oj.uz

답안 #643280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643280 2022-09-21T16:21:30 Z Kripton Sum Zero (RMI20_sumzero) C++14
100 / 100
 551 ms 18256 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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;
    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;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 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 3 ms 468 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 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 3 ms 468 KB Output is correct
7 Correct 64 ms 4684 KB Output is correct
8 Correct 57 ms 4612 KB Output is correct
9 Correct 74 ms 4756 KB Output is correct
10 Correct 69 ms 4672 KB Output is correct
11 Correct 60 ms 4588 KB Output is correct
12 Correct 76 ms 4700 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 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 3 ms 468 KB Output is correct
7 Correct 64 ms 4684 KB Output is correct
8 Correct 57 ms 4612 KB Output is correct
9 Correct 74 ms 4756 KB Output is correct
10 Correct 69 ms 4672 KB Output is correct
11 Correct 60 ms 4588 KB Output is correct
12 Correct 76 ms 4700 KB Output is correct
13 Correct 384 ms 17952 KB Output is correct
14 Correct 328 ms 17732 KB Output is correct
15 Correct 421 ms 18184 KB Output is correct
16 Correct 551 ms 17872 KB Output is correct
17 Correct 306 ms 17672 KB Output is correct
18 Correct 421 ms 18256 KB Output is correct