Submission #748517

#	Time	Username	Problem	Language	Result	Execution time	Memory
748517		doowey	Sum Zero (RMI20_sumzero)	C++14	61 / 100	306 ms	39260 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];
vector<int> Q[N];
int sol[N];
bool vis[N];

int path[N];
int iter = 0;

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

map<ll, int> en;

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);
        }
    }
    int q;
    cin >> q;
    int li, ri;
    int ans;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> li >> ri;
        sol[iq] = ri + 1;
        Q[li].push_back(iq);
    }
    for(int i = n + 1; i >= 1; i -- ){
        if(!vis[i]){
            dfs(i);
        }
    }
    for(int iq = 1; iq <= q; iq ++ ){
        cout << sol[iq] << "\n";
    }
    return 0;
}

Compilation message (stderr)

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

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