Submission #748536

#	Time	Username	Problem	Language	Result	Execution time	Memory
748536		doowey	Sum Zero (RMI20_sumzero)	C++14	61 / 100	278 ms	27160 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)4e5 + 10;

pii F[N];

int L[N], R[N];
pii Q[N];
int sol[N];
bool vis[N];

int path[N];
int iter = 0;
int q;
int lf, rf,mid, xi;
int bb;
void dfs(int u){
    path[iter] = u;
    iter ++ ;
    vis[u]=true;
    lf = 0;
    rf = q - 1;
    while(lf < rf){
        mid = (lf + rf) / 2;
        if(Q[mid].fi < u)
            lf = mid + 1;
        else
            rf = mid;
    }
    bb = lf;
    while(Q[bb].fi == u){
        xi = Q[bb].se;
        lf = 0, rf = iter - 1;
        while(lf < rf){
            mid = (lf + rf) / 2;
            if(path[mid] > sol[xi]){
                lf = mid + 1;
            }
            else{
                rf = mid;
            }
        }
        sol[xi] = iter - 1 - lf;
        bb ++ ;
    }
    for(int x = L[u]; x <= R[u]; x ++ ){
        dfs(x);
    }
    iter -- ;
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> F[i].fi;
        F[i].se = i;
    }
    F[n + 1].fi = 0;
    F[n + 1].se = n + 1;
    for(int i = n; i >= 1; i -- ){
        F[i].fi += F[i + 1].fi;
    }
    sort(F + 1, F + n + 2);
    for(int i = n + 1; i >= 1; i -- ){
        if(F[i].fi == F[i + 1].fi){
            sol[F[i].se] = F[i + 1].se;
        }
        L[i] = n + 2;
        R[i] = 0;
    }
    int low = n + 2;
    for(int i = n; i >= 1; i -- ){
        if(sol[i] != 0){
            low = min(low, sol[i]);
        }
        if(low < n + 2){
            L[low] = min(L[low], i);
            R[low] = max(R[low], i);
        }
    }
    cin >> q;
    int li, ri;
    int ans;
    for(int iq = 0; iq < q; iq ++ ){
        cin >> li >> ri;
        sol[iq] = ri + 1;
        Q[iq] = mp(li, iq);
    }
    sort(Q, Q + q);
    int cur;
    int nx;
    for(int i = n + 1; i >= 1; i -- ){
        if(!vis[i]){
            path[iter] = i;
            iter ++ ;
            while(iter > 0){
                cur = path[iter - 1];
                //cout << cur << " !\n";
                if(!vis[cur]){
                    vis[cur] = true;
                    lf = 0;
                    rf = q - 1;
                    while(lf < rf){
                        mid = (lf + rf) / 2;
                        if(Q[mid].fi < cur)
                            lf = mid + 1;
                        else
                            rf = mid;
                    }
                    bb = lf;
                    while(Q[bb].fi == cur){
                        xi = Q[bb].se;
                        lf = 0, rf = iter - 1;
                        while(lf < rf){
                            mid = (lf + rf) / 2;
                            if(path[mid] > sol[xi]){
                                lf = mid + 1;
                            }
                            else{
                                rf = mid;
                            }
                        }
                        sol[xi] = iter - 1 - lf;
                        bb ++ ;
                    }
                }
                if(L[cur] <= R[cur]){
                    nx = L[cur];
                    L[cur] ++ ;
                    path[iter] = nx;
                    iter ++ ;
                }
                else{
                    iter -- ;
                }
            }
        }
    }
    for(int iq = 0; iq < q; iq ++ ){
        cout << sol[iq] << "\n";
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:96:9: warning: unused variable 'ans' [-Wunused-variable]
   96 |     int ans;
      |         ^~~

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