oj.uz

Submission #643281

# Submission time Handle Problem Language Result Execution time Memory
643281 2022-09-21T16:27:03 Z Kripton Sum Zero (RMI20_sumzero) C++14
100 / 100
 433 ms 18232 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC pack(1)
using namespace std;
pair <long long,int> sum[400001];
int last[400001];
int best[5][400001];
int put[5];
bitset <400001> fraud;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,x,i,j;
    //cout << sizeof(pair<long long, int>)<<'\n';
    long long s=0;
    cin>>n;
    put[0]=1;
    for(i=1;i<=4;i++)
        put[i]=16*put[i-1];
    //cout<<put[4]<<'\n';
    best[0][0]=-1;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        s+=x;
        sum[i]={s,i};
    }
    sort(sum,sum+n+1);
    last[sum[0].second]=-1;
    for(i=1;i<=n;i++)
        if(sum[i].first==sum[i-1].first)
            last[sum[i].second]=sum[i-1].second;
        else
            last[sum[i].second]=-1;
    for(i=1;i<=n;i++)
    {
        best[0][i]=best[0][i-1];
        fraud[i]=1;
        if(last[i]>best[0][i])
        {
            best[0][i]=last[i];
            fraud[i]=0;
        }
        last[i]=i;
    }
    for(j=1;j<=4;j++)
        for(i=0;i<=n;i++)
        {
            int start=i;
            for(int l=1;l<=8;l++)
                if(start!=-1&&best[j-1][start]!=-1)
                {
                    best[j][i]=best[j-1][best[j-1][start]];
                    start=best[j-1][best[j-1][start]];
                }
                else
                    best[j][i]=-1;
        }
    int q,a,b;
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>a>>b;
        if(best[0][b]==-1)
        {
            cout<<"0\n";
            continue;
        }
        int rez=0;
        if(fraud[b])
        {
            b=best[0][b];
            rez=1;
        }
        if(b<a-1)
        {
            cout<<"0\n";
            continue;
        }
        int start=b,pas=4;
        while(pas!=-1)
        {
            for(j=1;j<=15;j++)
                if(best[pas][start]>=a-1)
                {
                    rez+=put[pas];
                    start=best[pas][start];
                }
            pas--;
        }
        cout<<rez<<'\n';
    }
    return 0;
}

Compilation message

sumzero.cpp:3: warning: ignoring '#pragma GCC pack' [-Wunknown-pragmas]
    3 | #pragma GCC pack(1)
      |

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 3 ms 596 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 576 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 3 ms 596 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Correct 64 ms 4676 KB Output is correct
8 Correct 59 ms 4560 KB Output is correct
9 Correct 81 ms 4744 KB Output is correct
10 Correct 64 ms 4696 KB Output is correct
11 Correct 58 ms 4556 KB Output is correct
12 Correct 72 ms 4756 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 3 ms 596 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Correct 64 ms 4676 KB Output is correct
8 Correct 59 ms 4560 KB Output is correct
9 Correct 81 ms 4744 KB Output is correct
10 Correct 64 ms 4696 KB Output is correct
11 Correct 58 ms 4556 KB Output is correct
12 Correct 72 ms 4756 KB Output is correct
13 Correct 374 ms 18088 KB Output is correct
14 Correct 309 ms 17804 KB Output is correct
15 Correct 418 ms 18140 KB Output is correct
16 Correct 377 ms 18016 KB Output is correct
17 Correct 306 ms 17668 KB Output is correct
18 Correct 433 ms 18232 KB Output is correct