Submission #748509

#	Time	Username	Problem	Language	Result	Execution time	Memory
748509		doowey	Sum Zero (RMI20_sumzero)	C++14	22 / 100	76 ms	26720 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];
 
vector<int> T[N];
vector<int> Q[N];
int sol[N];
bool vis[N];
 
int path[N];
int iter = 0;
int lf, rf, mid;

void dfs(int u){
    path[iter] = u;
    iter ++ ;
    vis[u]=true;
    for(auto xi : Q[u]){
        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;
    }
    for(auto x : T[u]){
        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;
        }
    }
    int low = n + 2;
    for(int i = n; i >= 1; i -- ){
        if(sol[i] != 0){
            low = min(low, sol[i]);
        }
        if(low < n + 2){
            T[low].push_back(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:83:9: warning: unused variable 'ans' [-Wunused-variable]
   83 |     int ans;
      |         ^~~

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