7 N log N ში მიწერია მაგრამ მაინც TLE_ს მაძლევს :-?
ვინმეს თუ გაქვთ გატარებული როგორ შეიძლება დავასწრაფო ?

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
 
typedef long long ll;
 
const int MAXN = 400000;
const int MAXM = 7;
 
 
int i, j, n, m, nn;
ll a[MAXN];
ll g[MAXN][MAXM];
ll idx[MAXN], f[MAXN];
 
 
int getIdx(int v){
	return min(v, MAXM - 1);
}
 
void push(int l, int r, int o){
	if (!f[o]) return;
	idx[o] = getIdx(idx[o] + f[o]);
	if (l != r){
		idx[2 * o] = getIdx(idx[2 * o] + f[o]);
		idx[2 * o + 1] = getIdx(idx[2 * o + 1] + f[o]);
		f[2 * o] += f[o];
		f[2 * o + 1] += f[o];
	}
	f[o] = 0;
}
 
void updatePoint(int l, int r, int o){
	if (l == r) return;
	g[o][idx[o]] = g[2 * o][idx[2 * o]] + g[2 * o + 1][idx[2 * o + 1]];
	return;
	int x, y, z;
	for (int w = 0; w < MAXM; w++){
		x = getIdx(idx[o] + w);
		y = getIdx(idx[2 * o] + w);
		z = getIdx(idx[2 * o + 1] + w);
		g[o][x] = g[2 * o][y] + g[2 * o + 1][z];
	}
}
 
void update(int l, int r, int v, int u, int o){
	if (l > u || r < v) return;
	if (l >= v && r <= u){
		f[o]++;
		push(l, r, o);
		return;
	}
	push(l, r, o);
	update(l, (l + r) / 2, v, u, 2 * o);
	update((l + r) / 2 + 1, r, v, u, 2 * o + 1);
	updatePoint(l, r, o);
}
 
ll find(int l, int r, int v, int u, int o){
	push(l, r, o);
	if (l > u || r < v) return 0;
	if (l >= v && r <= u) return g[o][idx[o]];
	return find(l, (l + r) / 2, v, u, 2 * o) +
	 find((l + r) / 2 + 1, r, v, u, 2 * o + 1);
}
 
 
int get(ll v){
	ll l, r, x;
	l = 1;
	r = min(v, 1000000001LL);
	while (l < r - 1){
		x = (l + r) / 2;
		if (x * x <= v)
			l = x;
		else r = x;
	}
	return x;
}
 
int main(){
 
 
	int x, y, z;
	int testCase = 0;
	while (scanf("%d",&n) == 1){
		testCase ++;
		if (testCase != 1)
			printf("\n");
		printf("Case #%d:\n", testCase);
		for (i = 0; i < n; i++)
			scanf("%I64d", &a[i]);
		for (nn = 1; nn < n; nn *= 2);
		for (i = 0; i < n; i++){
			g[nn + i][0] = a[i];
			for (j = 1; j < MAXM; j++)
				g[nn + i][j] = get(g[nn + i][j - 1]);
		}
		for (i = n; i < nn; i++)
			for (j = 0; j < MAXM; j++)
				g[nn + i][j] = 0;
 
		for (i = nn - 1; i >= 1; i--)
			for (j = 0; j < MAXM; j++)
				g[i][j]= g[2 * i][j] + g[2 * i + 1][j];
 
		for (i = 0; i < 2 * nn; i++)
			idx[i] = f[i] = 0;
 
		scanf("%d", &m);
		for (i = 0; i < m; i++){
			scanf("%d %d %d",&x, &y, &z);
			if (y > z) swap(y,z);
			if (x == 1)
				printf("%I64d\n", find(1, nn, y, z, 1));
			else update(1, nn, y, z, 1);
		}
 
 
	}
	return 0;
}

@brolia

SPOJ-ზე I64d სპეციფიკატორი მუშაობს ? შეიძლება ამის ბრალი იყოს ... ცადე lld

aazizian

TLE_ს არ მომცემდა მაგის ბრალი რომ იყოს.

პ.ს.
Elle
ეს თემა ერთხელ გავხსენი და მიჩვენებს თითქოს 2 ჯერ გავხსენი :-?