oj.uz

Submission #850794

# Submission time Handle Problem Language Result Execution time Memory
850794 2023-09-17T12:52:44 Z alexdd Sum Zero (RMI20_sumzero) C++17
100 / 100
 715 ms 20304 KB 
#include<bits/stdc++.h>
using namespace std;
const int val1 = 80;
const int logval = 3;
int n;
int anc[400005][logval];
int v[400005];
long long vals[400005];
int ult[400005];
/// 500000 * (4 + 4 + 8 + x*4) <= 20 000 000
/// 500000 * 16 + 500000 * x*4 <= 20 000 000
/// x <= 6
int put[logval];
void calc_anc()
{
    for(int p=1;p<logval;p++)
    {
        for(int i=1;i<=n+2;i++)
        {
            anc[i][p]=anc[i][p-1];
            for(int j=0;j<val1-1;j++)
                anc[i][p]=anc[anc[i][p]][p-1];
        }
    }
}
int norma(long long x)
{
    return (lower_bound(vals,vals+1+n,x) - vals);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    put[0]=1;
    for(int i=1;i<logval;i++)
        put[i]=put[i-1]*val1;
    long long tot=0;
    cin>>n;
    int a;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        vals[i]=vals[i-1]+v[i];
        tot+=v[i];
    }
    sort(vals,vals+1+n);
    long long suff=0;
    anc[n+1][0]=n+2;
    anc[n+2][0]=n+2;
    for(int i=n;i>0;i--)
    {
        anc[i][0]=anc[i+1][0];
        ult[norma(tot-suff)]=i;
        suff+=v[i];
        if(ult[norma(tot-suff)]!=0)
            anc[i][0]=min(anc[i][0], ult[norma(tot-suff)]+1);
    }
    calc_anc();
    int cntq,b;
    cin>>cntq;
    for(int i=0;i<cntq;i++)
    {
        cin>>a>>b;
        int rez=0;
        for(int p=logval-1;p>=0;p--)
        {
            for(int j=0;j<val1-1;j++)
            {
                if(anc[a][p]-1<=b)
                {
                    rez+=put[p];
                    a=anc[a][p];
                }
            }
        }
        cout<<rez<<"\n";
    }
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2392 KB Output is correct
2 Correct 5 ms 2392 KB Output is correct
3 Correct 6 ms 2392 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Correct 6 ms 2392 KB Output is correct
7 Correct 132 ms 8064 KB Output is correct
8 Correct 107 ms 7992 KB Output is correct
9 Correct 144 ms 8016 KB Output is correct
10 Correct 129 ms 8016 KB Output is correct
11 Correct 116 ms 8016 KB Output is correct
12 Correct 144 ms 8016 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2392 KB Output is correct
2 Correct 5 ms 2392 KB Output is correct
3 Correct 6 ms 2392 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Correct 6 ms 2392 KB Output is correct
7 Correct 132 ms 8064 KB Output is correct
8 Correct 107 ms 7992 KB Output is correct
9 Correct 144 ms 8016 KB Output is correct
10 Correct 129 ms 8016 KB Output is correct
11 Correct 116 ms 8016 KB Output is correct
12 Correct 144 ms 8016 KB Output is correct
13 Correct 598 ms 13296 KB Output is correct
14 Correct 497 ms 12592 KB Output is correct
15 Correct 715 ms 13648 KB Output is correct
16 Correct 617 ms 13188 KB Output is correct
17 Correct 482 ms 20304 KB Output is correct
18 Correct 706 ms 20280 KB Output is correct