Submission #1312439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312439		seriousgrey	Sum Zero (RMI20_sumzero)	C++20	22 / 100	174 ms	40908 KiB

sumzero

#pragma GCC optimize("O3,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
using namespace std;
// #ifdef ONLINE_JUDGE
// #define debug(...) 42
// #else
// #include "debug.h"
// #endif
#define int long long
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
#define print(x) do{ cout << x << endl; return; } while(0)
#define OmPatel() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define sz(x) (int)(x).size()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define fr(i,n) for(int i = 0; i < (n); ++i)
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define per(i,a,b) for(int i = (a); i >= (b); --i)

// Global
const int MAXX = 400'001;
const int LOG = 20;
// Main Function
void solve() {
    int n; cin>>n;
    vi c(n),pref(n,0);
    unordered_map<int,vi> mpp;
    mpp[0].pb(-1);
    fr(i,n){
        cin>>c[i];
        if(i==0) pref[i] = c[i];
        else pref[i] = pref[i-1]+c[i];
        mpp[pref[i]].pb(i);
    }
    vi nxt(n);
    fr(i,n){
        int req = 0;
        if(i) req = pref[i-1];
        if(!mpp.count(req)){
            nxt[i] = n;
            continue;
        }
        auto it =lower_bound(all(mpp[req]),i);
        if(it!=mpp[req].end()) nxt[i] = *it;
        else nxt[i] = n;
    }
    vi best(n+1,n);
    per(i,n-1,0) best[i] = min(nxt[i],best[i+1]);
    vi go(n+1,n);
    fr(i,n){
        if(best[i]!=n) go[i] = best[i]+1;
    }
    vector<vi> pos(LOG,vi(n+1,n)),cnt(LOG,vi(n+1,0));
    fr(i,n+1) pos[0][i] = go[i];
    fr(i,n) cnt[0][i] = (best[i]==n?0:1);
    cnt[0][n] = 0;
    rep(k,1,LOG-1) fr(i,n+1){
        int mid = pos[k-1][i];
        pos[k][i] = (mid<=n?pos[k-1][mid]:n);
        cnt[k][i] = cnt[k-1][i]+(mid<=n?cnt[k-1][mid]:0);
    }
    int q; cin>>q;
    while(q--){
        int l,r; cin>>l>>r;
        --l,--r;
        int p = l,ans =0;
        per(k,LOG-1,0){
            if(p==n) break;
            int np = pos[k][p];
            if(np<=r+1 and cnt[k][p]){
                ans+=cnt[k][p];
                p = np;
            }
        }
        cout<<ans<<endl;
    }
}

signed main() {
    OmPatel();
    int _ = 1;
    // cin >> _;
    while (_-- > 0) solve();
    return 0;
}

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