Submission #748428

#	Time	Username	Problem	Language	Result	Execution time	Memory
748428		doowey	Sum Zero (RMI20_sumzero)	C++14	22 / 100	92 ms	28740 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, 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;
const int LOG = 19;

ll c[N];

vector<int> T[N];
vector<pii> Q[N];

int sol[N];
bool vis[N];

vector<int> path;

void dfs(int u){
    path.push_back(u);
    vis[u]=true;
    for(auto xi : Q[u]){
        int lf = 0, rf = (int)path.size() - 1;
        int mid;
        while(lf < rf){
            mid = (lf + rf) / 2;
            if(path[mid] > xi.fi){
                lf = mid + 1;
            }
            else{
                rf = mid;
            }
        }
        sol[xi.se] = path.size() - 1 - lf;
    }
    for(auto x : T[u]){
        dfs(x);
    }
    path.pop_back();
}
int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> c[i];
    }
    ll suff = 0;
    map<ll, int> en;
    en[0ll] = n + 1;
    int low = n + 2;
    for(int i = n; i >= 1; i -- ){
        suff += c[i];
        if(en.count(suff)){
            low = min(low, en[suff]);
        }
        if(low < n + 2)
            T[low].push_back(i);
        //cout << i << " -> " << low << "\n";
        en[suff] = i;
    }
    int q;
    cin >> q;
    int li, ri;
    int ans;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> li >> ri;
        Q[li].push_back(mp(ri + 1, 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:73:9: warning: unused variable 'ans' [-Wunused-variable]
   73 |     int ans;
      |         ^~~

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