oj.uz

Submission #646901

# Submission time Handle Problem Language Result Execution time Memory
646901 2022-09-30T23:19:22 Z DobromirAngelov Sum Zero (RMI20_sumzero) C++14
100 / 100
 269 ms 15048 KB 
#pragma optimize "O3"
#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;
}

Compilation message

sumzero.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize "O3"
      |

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 4 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 4 ms 468 KB Output is correct
7 Correct 56 ms 3912 KB Output is correct
8 Correct 57 ms 3780 KB Output is correct
9 Correct 61 ms 3916 KB Output is correct
10 Correct 56 ms 3908 KB Output is correct
11 Correct 62 ms 3780 KB Output is correct
12 Correct 62 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 4 ms 468 KB Output is correct
7 Correct 56 ms 3912 KB Output is correct
8 Correct 57 ms 3780 KB Output is correct
9 Correct 61 ms 3916 KB Output is correct
10 Correct 56 ms 3908 KB Output is correct
11 Correct 62 ms 3780 KB Output is correct
12 Correct 62 ms 3916 KB Output is correct
13 Correct 244 ms 14752 KB Output is correct
14 Correct 254 ms 14616 KB Output is correct
15 Correct 269 ms 15048 KB Output is correct
16 Correct 242 ms 14832 KB Output is correct
17 Correct 254 ms 14488 KB Output is correct
18 Correct 267 ms 15004 KB Output is correct