oj.uz

Submission #646902

# Submission time Handle Problem Language Result Execution time Memory
646902 2022-09-30T23:19:56 Z DobromirAngelov Sum Zero (RMI20_sumzero) C++14
100 / 100
 271 ms 15052 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAXN=4e5+5;
const int INF=1e9+5;

int n,q;
pair<long long,int> pref[MAXN];
//int previous[MAXN];
int prv[MAXN];
int nxt_l[MAXN], r[MAXN];
int ans[MAXN];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin>>n;
for(int i=1;i<=n;i++) cin>>pref[i].first;

for(int i=1;i<=n;i++)
{
    pref[i].first=pref[i-1].first+pref[i].first;
    pref[i].second=i;
}
sort(pref,pref+n+1);
for(int i=0;i<=n;i++) nxt_l[i]=INF;
for(int i=0;i<=n;i++)
{
    if(pref[i].first==pref[i+1].first) nxt_l[pref[i].second]=pref[i+1].second;
}

int ptr=n;
for(int i=n;i>=0;i--)
{
    while(ptr>=nxt_l[i])
    {
        pref[ptr].second=i+1;
        ptr--;
    }
}
for(;ptr>=0;ptr--) pref[ptr].second=0;
cin>>q;
for(int i=1;i<=q;i++)
{
    cin>>nxt_l[i]>>r[i];
}

for(int lg=18;lg>=0;lg--)
{
    for(int i=1;i<=n;i++) prv[i]=pref[i].second;

    for(int j=1;j<=lg;j++)
    {
        for(int i=n;i>0;i--)
        {
            if(prv[i]>1) prv[i]=prv[prv[i]-1];
            else prv[i]=0;
        }
    }

    for(int i=1;i<=q;i++)
    {
        if(nxt_l[i]<=r[i] && prv[r[i]]>=nxt_l[i])
        {
            ans[i]+=(1<<lg);
            r[i]=prv[r[i]]-1;
        }
    }
}

for(int i=1;i<=q;i++) cout<<ans[i]<<endl;

return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 59 ms 3840 KB Output is correct
8 Correct 56 ms 3800 KB Output is correct
9 Correct 62 ms 3900 KB Output is correct
10 Correct 59 ms 3912 KB Output is correct
11 Correct 63 ms 3844 KB Output is correct
12 Correct 60 ms 3916 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 59 ms 3840 KB Output is correct
8 Correct 56 ms 3800 KB Output is correct
9 Correct 62 ms 3900 KB Output is correct
10 Correct 59 ms 3912 KB Output is correct
11 Correct 63 ms 3844 KB Output is correct
12 Correct 60 ms 3916 KB Output is correct
13 Correct 255 ms 14824 KB Output is correct
14 Correct 259 ms 14492 KB Output is correct
15 Correct 271 ms 15052 KB Output is correct
16 Correct 248 ms 14692 KB Output is correct
17 Correct 253 ms 14528 KB Output is correct
18 Correct 269 ms 14960 KB Output is correct