#include <bits/stdc++.h>
#define kyou using
#define mo namespace
#define kawaii std
kyou mo kawaii; // hi honey~
#define ll long long
#define ld long double
#define endl "\n"
const int MX = 400005;
const int LG = 5;
// const int BLOCK = 205;
// const int inf = 1000000069;
// const ll inf_ll = 8000000000000000069ll;
// const ll mod = 1e9 + 7;
// const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
// const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
// const int dx[] = {0, 1, 0, -1, 0, 0};
// const int dy[] = {1, 0, -1, 0, 0, 0}; // adj
// const int dz[] = {0, 0, 0, 0, 1, -1}; // 3d
// const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
// const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
bool untied = 0;
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
if(!untied) unsyncIO(), untied = 1;
if(s.size()){
setIn(s + ".in");
setOut(s + "_output.out");
}
}
const int H = (1 << 19) - 1;
ll key[H + 1];
int val[H + 1];
int &last(ll k){
int i = (int)(k & H);
while(val[i] != 0 && key[i] != k)
i = (i + 1) & H;
key[i] = k;
return val[i];
}
int n, q;
ll v[MX];
int anc[MX][LG], pw10[LG + 1];
int main(){
pw10[0] = 1;
for(int i = 1; i <= LG; i ++)
pw10[i] = pw10[i - 1] * 10;
cin.tie(0) -> sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> v[i];
for(int i = 1; i <= n; i ++)
v[i] += v[i - 1];
last(v[n]) = n;
anc[n][0] = n + 1;
for(int i = n - 1; i >= 0; i --){
int &tp = last(v[i]);
if(tp && tp < anc[i + 1][0]) anc[i][0] = tp;
else anc[i][0] = anc[i + 1][0];
tp = i;
}
for(int j = 1; j < LG; j ++){
for(int i = 0; i <= n; i ++){
if(anc[i][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[i][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[i][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
else anc[i][j] = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1];
}
}
cin >> q;
for(int l, r, i = 0; i < q; i ++){
cin >> l >> r;
l --;
int ans = 0, nw = l;
for(int j = LG; j >= 0; j --){
for(int tp = 0; tp < 10; tp ++){
if(j == LG){
int cr;
if(anc[nw][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[nw][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[nw][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
else cr = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1];
if(cr <= r){
ans += pw10[j];
nw = cr;
}
}else{
if(anc[nw][j] <= r){
ans += pw10[j];
nw = anc[nw][j];
}else break;
}
}
}
cout << ans << endl;
}
}
Compilation message
sumzero.cpp: In function 'void setIn(std::string)':
sumzero.cpp:29:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp: In function 'void setOut(std::string)':
sumzero.cpp:30:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
588 KB |
Output is correct |
| 4 |
Correct |
4 ms |
844 KB |
Output is correct |
| 5 |
Correct |
3 ms |
460 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
588 KB |
Output is correct |
| 4 |
Correct |
4 ms |
844 KB |
Output is correct |
| 5 |
Correct |
3 ms |
460 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
77 ms |
8064 KB |
Output is correct |
| 8 |
Correct |
62 ms |
4036 KB |
Output is correct |
| 9 |
Correct |
78 ms |
3732 KB |
Output is correct |
| 10 |
Correct |
78 ms |
8080 KB |
Output is correct |
| 11 |
Correct |
62 ms |
3812 KB |
Output is correct |
| 12 |
Correct |
77 ms |
3992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
844 KB |
Output is correct |
| 2 |
Correct |
3 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
588 KB |
Output is correct |
| 4 |
Correct |
4 ms |
844 KB |
Output is correct |
| 5 |
Correct |
3 ms |
460 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
77 ms |
8064 KB |
Output is correct |
| 8 |
Correct |
62 ms |
4036 KB |
Output is correct |
| 9 |
Correct |
78 ms |
3732 KB |
Output is correct |
| 10 |
Correct |
78 ms |
8080 KB |
Output is correct |
| 11 |
Correct |
62 ms |
3812 KB |
Output is correct |
| 12 |
Correct |
77 ms |
3992 KB |
Output is correct |
| 13 |
Correct |
465 ms |
19276 KB |
Output is correct |
| 14 |
Correct |
373 ms |
15620 KB |
Output is correct |
| 15 |
Correct |
485 ms |
13956 KB |
Output is correct |
| 16 |
Correct |
432 ms |
19516 KB |
Output is correct |
| 17 |
Correct |
337 ms |
14984 KB |
Output is correct |
| 18 |
Correct |
455 ms |
13920 KB |
Output is correct |
