Submission #942691

#	Time	Username	Problem	Language	Result	Execution time	Memory
942691		socpite	Sum Zero (RMI20_sumzero)	C++14	0 / 100	7 ms	25432 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;

const int maxn = 4e5+5;

int n;
pair<long long, int> A[maxn];
int mx[maxn], vis[maxn], ans[maxn];

vector<int> tree[maxn];
vector<pair<int, int>> queries[maxn];

vector<int> stk;

void dfs(int x){
    vis[x] = 1;
    for(auto qq: queries[x]){
        // cout << "SUS " << qq.second << " " << *lower_bound(stk.begin(), stk.end(), qq.first - 1) << endl;
        ans[qq.second] = stk.end() - lower_bound(stk.begin(), stk.end(), qq.first - 1);
    }
    stk.push_back(x);
    for(auto v: tree[x]){
        dfs(v);
    }
    stk.pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    memset(mx, -1, sizeof(mx));
    for(int i = 1; i <= n; i++){
        cin >> A[i].first;
        A[i].first += A[i-1].first;
        A[i].second = i;
    }
    sort(A, A+n+1);
    for(int i = 1; i <= n; i++){
        if(A[i].first == A[i-1].first)mx[A[i].second] = A[i-1].second;
    }
    for(int i = 0; i <= n; i++){
        if(i)mx[i] = max(mx[i], mx[i-1]);
        if(mx[i] != -1)tree[mx[i]].push_back(i);
        // cout << mx[i] << " " << i << endl;
    }
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        queries[r].push_back({l, i});
    }
    for(int i = 0; i <= n; i++)if(!vis[i])dfs(i);
    for(int i = 0; i < q; i++)cout << ans[i] << "\n";
}

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