Submission #1352939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352939		bakhtiyarn	Sum Zero (RMI20_sumzero)	C++20	61 / 100	237 ms	56848 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5+5;
int up[N][20];
vector<int> idx[N];

// for(int i=1; i<=n; i++)
void solve(){
    int n; cin >> n;


    unordered_map<int, int> last;
    int pre = 0;
    for(int i=0; i<=n; i++) {
        if(i) {int x; cin >> x; pre += x; }
        
        if(last.count(pre)) up[i][0] = last[pre];
        else up[i][0] = -1;
        last[pre] = i;

        if(up[i][0] != -1) idx[up[i][0]].push_back(i);
    }
    last.clear();


    int mn = 1e18;
    for(int i=n; i>=0; i--){
        for(int j: idx[i]) mn = min(mn, j);
        idx[i].clear();

        if(mn == 1e18) up[i][0] = n+1;
        else up[i][0] = mn;

        for(int k=1; k<20; k++) {
            if (up[i][k-1] > n) up[i][k] = n + 1;
            else up[i][k] = up[up[i][k-1]][k-1];
        }
    }

    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r; l--;
        long long ans = 0;
        for(int b=19; b>=0; b--){
            if(up[l][b] > r) continue;
            ans += 1<<b;
            l = up[l][b];
        }
        cout << ans << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message (stderr)

sumzero.cpp: In function 'void solve()':
sumzero.cpp:27:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   27 |     int mn = 1e18;
      |              ^~~~

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