oj.uz

Submission #942682

# Submission time Handle Problem Language Result Execution time Memory
942682 2024-03-11T02:51:07 Z fdnfksd Sum Zero (RMI20_sumzero) C++14
100 / 100
 449 ms 18168 KB 
#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=4e5+100;
const ll inf=1e18;
const ll mod=1e9+7;
ll n;
pli a[maxn];
int nxt[maxn],mn[maxn],p[maxn][6],pw[10];
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i].fi,a[i].fi+=a[i-1].fi,a[i].se=i;
    sort(a,a+n+1);
    for(int i=0;i<=n;i++)
    {
        if(i<n&&a[i].fi==a[i+1].fi) nxt[a[i].se+1]=a[i+1].se;
        else nxt[a[i].se+1]=n+1;
    }
    nxt[n+1]=n+1;
    mn[n+1]=n+1;
    for(int i=n;i>=1;i--)
    {
        if(nxt[i]<nxt[mn[i+1]]) mn[i]=i;
        else mn[i]=mn[i+1];
    }
    for(int i=n;i>=1;i--)
    {
        ll u=nxt[i];
        if(u==n+1)
        {
            p[i][0]=n+1;
        }
        else
        {
            u++;
            p[i][0]=mn[u];
        }
    }
    p[n+1][0]=n+1;
    for(int j=1;j<=5;j++)
    {
        for(int i=1;i<=n+1;i++)
        {
            ll x=i;
            for(int k=0;k<10;k++)
            {
                x=p[x][j-1];
            }
            p[i][j]=x;
        }
    }
    pw[0]=1;
    for(int i=1;i<=6;i++) pw[i]=pw[i-1]*10;
    ll q;
    cin >> q;
    for(int i=1;i<=q;i++)
    {
        ll l,r,ans=0;
        cin >> l >> r;
        l=mn[l];
        if(nxt[l]>r) {cout << 0 << '\n';continue;}
        else ans++;
        //cout << nxt[l] << '\n';
        for(int j=5;j>=0;j--)
        {
            for(int k=0;k<9;k++)
            {
                if(nxt[p[l][j]]<=r)
                {
                    l=p[l][j];
                    ans+=pw[j];
                }
                else break;
            }
        }
        cout << ans << '\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6744 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 61 ms 11144 KB Output is correct
8 Correct 53 ms 11244 KB Output is correct
9 Correct 68 ms 11348 KB Output is correct
10 Correct 64 ms 11088 KB Output is correct
11 Correct 54 ms 11088 KB Output is correct
12 Correct 68 ms 11348 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6744 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 61 ms 11144 KB Output is correct
8 Correct 53 ms 11244 KB Output is correct
9 Correct 68 ms 11348 KB Output is correct
10 Correct 64 ms 11088 KB Output is correct
11 Correct 54 ms 11088 KB Output is correct
12 Correct 68 ms 11348 KB Output is correct
13 Correct 347 ms 18028 KB Output is correct
14 Correct 278 ms 17700 KB Output is correct
15 Correct 368 ms 18144 KB Output is correct
16 Correct 449 ms 18072 KB Output is correct
17 Correct 337 ms 18000 KB Output is correct
18 Correct 368 ms 18168 KB Output is correct