Submission #853930

#	Time	Username	Problem	Language	Result	Execution time	Memory
853930		divad	Sum Zero (RMI20_sumzero)	C++14	61 / 100	1034 ms	24400 KiB

sumzero

#include <bits/stdc++.h>
#define ends saradanciu
using namespace std;
const int BASE = 4;
const int LMAX = 7;
const int NMAX = 4e5+2;
int n,q,c,x,y,nxt[LMAX][NMAX];
int ends[NMAX],pwr[LMAX];

ifstream fin("test.in");
ofstream fout("test.out");

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef ONPC
    #define cin fin
#endif // ONPC
    pwr[0] = 1;
    for(int i = 1; i < LMAX; i++){
        pwr[i] = pwr[i-1]*BASE;
    }
    cin >> n;
    map<int, int> mp;
    int pref = 0;
    mp[pref] = 0;
    for(int i = 1; i <= n; i++){
        cin >> c;
        pref += c;
        if(mp.count(pref)){
            ends[mp[pref]+1] = i;
        }
        mp[pref] = i;
    }
    nxt[0][n+1] = n+2;
    int mini = n+2;
    for(int i = n; i >= 1; i--){
        if(ends[i] != 0){
            mini = min(mini, ends[i]);
        }
        nxt[0][i] = mini+1;
    }
    for(int j = 1; j <= 2; j++){
        for(int i = 1; i <= n+1; i++){
            nxt[1][i] = nxt[(j != 1)][nxt[(j != 1)][i]];
        }
        for(int i = 1; i <= n+1; i++){
            if(nxt[1][i] == 0){
                nxt[1][i] = n+2;
            }
        }
    }
    for(int j = 2; j < LMAX; j++){
        for(int i = 1; i <= n+1; i++){
            nxt[j][i] = i;
            for(int k = 1; k <= BASE; k++){
                nxt[j][i] = nxt[j-1][nxt[j][i]];
            }
        }
        for(int i = 1; i <= n+1; i++){
            if(nxt[j][i] == 0){
                nxt[j][i] = n+2;
            }
        }
    }
    cin >> q;
    int ct = 0;
    while(q--){
        cin >> x >> y;
        int ans = 0;
        int len = y-x+1;
        for(int i = LMAX-1; i >= 0; i--){
            while(nxt[i][x]-1 <= y){
                ans += pwr[i];
                x = nxt[i][x];
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:72:13: warning: unused variable 'len' [-Wunused-variable]
   72 |         int len = y-x+1;
      |             ^~~
sumzero.cpp:68:9: warning: unused variable 'ct' [-Wunused-variable]
   68 |     int ct = 0;
      |         ^~

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39