This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 400000
#define MAXL 20
int rmq[MAXL / 4][MAXN + 6], fr[MAXN + 1], pozs[MAXN + 1];
long long v[MAXN + 1];
char cmp(int x, int y) {
return v[x] < v[y];
}
int readInt() {
int x, semn;
char ch;
ch = fgetc(stdin);
while (isspace(ch)) {
ch = fgetc(stdin);
}
semn = 1;
if (ch == '-') {
semn = -1;
ch = fgetc(stdin);
}
x = 0;
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = fgetc(stdin);
}
return x * semn;
}
int calcPoz(int j, int i) {
if (j % 4 == 0) {
return rmq[j / 4][i];
} else if (j % 4 == 1) {
return rmq[j / 4][rmq[j / 4][i] + 1];
} else if (j % 4 == 2) {
return rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][i] + 1] + 1] + 1];
} else {
return rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][rmq[j / 4][i] + 1] + 1] + 1] + 1] + 1] + 1] + 1];
}
}
int main()
{
int n, q, i, poz, j, p, p2, st, dr, rez, x0, x;
long long y;
//fac sume partiale si secv st dr are suma 0 daca sp[dr] = sp[st - 1]
//deci trebuie sa caut numere egale dupa ce fac sume partiale
//la fiecare interval gasesc prima pereche de nr egale, cea in care poz din dr este cat mai mica si dupa
//tin cu un binary lifting care sunt urmatoarele si vad asa cate sunt pana la dr
//scot jumatate din rmq ca sa nu iau mle
n = readInt();
for (i = 1; i <= n; i++) {
v[i] = v[i - 1] + readInt();
rmq[0][i] = n + 1;
pozs[i] = i;
}
sort(pozs + 1, pozs + n + 1, cmp);
y = v[pozs[1]];
v[pozs[1]] = x = 1;
x0 = -1;
for (i = 2; i <= n; i++) {
if (v[pozs[i]] != y) {
x++;
}
if (v[pozs[i]] == 0) {
x0 = x;//un 0 normalizat
}
y = v[pozs[i]];
v[pozs[i]] = x;
}
for (i = 1; i <= n; i++) {
if (v[i] != x0 && fr[v[i]] == 0) {
fr[v[i]] = i;
} else {
poz = fr[v[i]] + 1;
if (i < rmq[0][poz]) {
rmq[0][poz] = i;
}
fr[v[i]] = i;
}
}
for (i = n - 1; i > 0; i--) {
if (rmq[0][i + 1] < rmq[0][i]) {
rmq[0][i] = rmq[0][i + 1];
}
}
rmq[0][n + 1] = rmq[0][n + 2] = rmq[0][n + 3] = rmq[0][n + 4] = rmq[0][n + 5] = n + 1;//santinele
//in pozdr[i] este pozitia minima a unui capat dr, pentr un st >= i
j = p = 1;
while (p <= n) {
if (j % 4 == 0) {
for (i = 1; i <= n + 2; i++) {
rmq[j / 4][i] = rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][rmq[j / 4 - 1][i] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1] + 1];
}
}
j++;
p *= 2;
}
q = readInt();
p2 = 0;
while ((1 << p2) <= n) {
p2++;
}
p2--;
for (i = 0; i < q; i++) {
st = readInt();
dr = readInt();
rez = 0;
for (p = p2; p >= 0; p--) {
if (calcPoz(p, st) <= dr) {
rez += (1 << p);
st = calcPoz(p, st) + 1;
}
}
printf("%d\n", rez);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |