Submission #1352938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352938		bakhtiyarn	Sum Zero (RMI20_sumzero)	C++20	61 / 100	231 ms	51792 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;
    
    for(int i=1; i<=n; i++) {int x; cin >> x; up[i][0] = up[i-1][0] + x; };


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

    for(int i=0; i<=n; i++) if(up[i][0] != -1) idx[up[i][0]].push_back(i);

    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 i=n; i>=0; i--){
        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:26:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   26 |     int mn = 1e18;
      |              ^~~~

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