Submission #597357

#	Time	Username	Problem	Language	Result	Execution time	Memory
597357		definitelynotmee	Sum Zero (RMI20_sumzero)	C++17	0 / 100	3 ms	596 KiB

sumzero

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename t>
using matrix = vector<vector<t>>;

int main(){
    
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n;

    vector<ll> pref(n+1), rpref(n+2);
    set<ll> s = {0};
    map<ll,ll> m;

    for(int i = 1; i <= n; i++){
        cin >> pref[i];
        rpref[i] = pref[i];
        pref[i]+=pref[i-1];
        s.insert(pref[i]);
    }

    for(ll i : s){
        m[i] = m.size();
    }
    

    for(int i = 0; i <= n; i++)
        pref[i] = m[pref[i]];

    vector<int> last(n+1,-1);
    last[m[0]] = 1;

    s.clear();
    m.clear();
    s.insert(0);

    for(int i = n; i> 0 ;i--) 
        rpref[i] += rpref[i+1], s.insert(rpref[i]);

    for(ll i : s)
        m[i] = m.size();
    for(int i = 1; i <= n; i++){
        rpref[i] = m[rpref[i]];
    }
    

    vector<int> dp(n+1), jmp(n+2, n+2);
    

    for(int i = 1; i <= n; i++)
        dp[i] = max(dp[i-1], last[pref[i]]!=-1 ? dp[last[pref[i]]]+1:-1), last[pref[i]] = i;
    
    fill(all(last),n+2);
    last[m[0]] = n+1;

    for(int i = n; i > 0; i--){
        jmp[i] = min(jmp[i+1], last[rpref[i]]);
        last[rpref[i]] = i;
    }

    // for(int i = 1; i<= n; i++){
    //     cout << jmp[i] << ' ';
    // }
    // cout << '\n';
    cin >> q;

    while(q--){
        int l, r;
        cin >> l >> r;
        
        int nextrange = jmp[l]-1;
        if(nextrange > r){
            cout << 0 << '\n';
            continue;
        }

        cout << dp[r]-dp[nextrange]+1 << '\n';
        
    }

}

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