| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 786600 | Cookie | Sum Zero (RMI20_sumzero) | C++14 | 0 ms | 0 KiB |
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>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e15 + 7, inf = 1e16;
const int mxn = 4e5 + 5, base = 128;
int n, q;
int up[mxn + 1][3], a[mxn + 1], pw[5];
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
map<int, int>mp; mp[0] = n + 1;
ll sm = 0;
for(int i = n; i >= 1; i--){
sm += 1LL * a[i];
if(mp.find(sm) != mp.end()){
a[i] = mp[sm] - 1;
}else{
a = n + 1;
}
mp[sm] = i;
}
mp.clear();
int mn = n + 1;
up[n + 1][0] = n + 1;
for(int i = n; i >= 1; i--){
mn = min(mn, to[i]);
up[i][0] = mn;
}
for(int i = 1; i < 3; i++){
for(int j = 1; j <= n + 1; j++){
int v = j;
for(int k = 0; k < base; k++){
v = up[v][i - 1] + 1;
if(v >= n + 1){
v = n + 2; break;
}
}
up[j][i] = v - 1;
//cout << i << " " << j << ' ' << up[j][i] << "\n";
}
}
pw[0] = 1;
for(int i = 1; i < 3; i++)pw[i] = pw[i - 1] * base;
cin >> q;
while(q--){
int l, r; cin >> l >> r;
int ans = 0;
for(int i = 2; i >= 0; i--){
while(1){
if(up[l][i] <= r){
ans += pw[i]; l = up[l][i] + 1;
}else{
break;
}
}
}
cout << ans << "\n";
}
return(0);
}