oj.uz

Submission #478282

# Submission time Handle Problem Language Result Execution time Memory
478282 2021-10-06T19:22:22 Z Tenis0206 Sum Zero (RMI20_sumzero) C++11
61 / 100
 83 ms 13528 KB 
#include <bits/stdc++.h>

using namespace std;
int n,q,v[100005];
vector<int> G[100005];
vector<pair<int,int>> Q[100005];
int t;
unordered_map<long long,int> mp;
int l[100005];
int cnt = 0;
void dfs(int nod)
{
    l[cnt++] = nod;
    for(auto it : Q[nod])
    {
        int st = 1;
        int dr = cnt-1;
        int poz = 0;
        while(st<=dr)
        {
            int mij = (st+dr)>>1;
            if(l[mij]-1<=it.first)
            {
                poz = mij;
                dr = mij-1;
            }
            else
            {
                st = mij+1;
            }
        }
        v[it.second] = cnt - poz - 1;
    }
    for(auto it : G[nod])
    {
        dfs(it);
    }
    --cnt;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 //   freopen("sumzero.in","r",stdin);
 //   freopen("sumzero.out","w",stdout);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        int st,dr;
        cin>>st>>dr;
        Q[st].push_back({dr,i});
    }
    mp[0] = n+1;
    G[0].push_back(n+1);
    t = 0;
    long long sum = 0;
    for(int i=n; i>=1; i--)
    {
        sum+=v[i];
        if(mp[sum])
        {
            if(t)
            {
                t = min(t,mp[sum]);
            }
            else
            {
                t = mp[sum];
            }
        }
        G[t].push_back(i);
        mp[sum] = i;
    }
    dfs(0);
    for(int i=1; i<=q; i++)
    {
        cout<<v[i]<<'\n';
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 9 ms 5324 KB Output is correct
4 Correct 6 ms 5324 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct
6 Correct 8 ms 5452 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 9 ms 5324 KB Output is correct
4 Correct 6 ms 5324 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct
6 Correct 8 ms 5452 KB Output is correct
7 Correct 71 ms 11372 KB Output is correct
8 Correct 71 ms 13528 KB Output is correct
9 Correct 69 ms 11264 KB Output is correct
10 Correct 83 ms 12688 KB Output is correct
11 Correct 81 ms 12764 KB Output is correct
12 Correct 69 ms 11236 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 9 ms 5324 KB Output is correct
4 Correct 6 ms 5324 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct
6 Correct 8 ms 5452 KB Output is correct
7 Correct 71 ms 11372 KB Output is correct
8 Correct 71 ms 13528 KB Output is correct
9 Correct 69 ms 11264 KB Output is correct
10 Correct 83 ms 12688 KB Output is correct
11 Correct 81 ms 12764 KB Output is correct
12 Correct 69 ms 11236 KB Output is correct
13 Incorrect 9 ms 5840 KB Output isn't correct
14 Halted 0 ms 0 KB -