oj.uz

Submission #851561

# Submission time Handle Problem Language Result Execution time Memory
851561 2023-09-20T06:50:37 Z heeheeheehaaw Sum Zero (RMI20_sumzero) C++17
100 / 100
 692 ms 20472 KB 
#include<bits/stdc++.h>

using namespace std;

int n;
const int baza = 80, lg = 3;
int v[400005], bl[400005][3];
long long vals[400005];
int mp[400005];

int query(int u, int v)
{
    int rez = 0, put = 80 * 80;
    for(int j = 2; j >= 0; j--)
    {
        for(int i = 1; i <= 79; i++)
            if(bl[u][j] <= v)
            {
                u = bl[u][j];
                rez += put;
            }
        put /= 80;
    }

    return rez;
}
int norma(long long x)
{
    return (lower_bound(vals,vals+1+n,x) - vals);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int q;
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>v[i];
    long long mindr = n + 1, sum = 0;
    for(int i = n; i >= 1; i--)
    {
        sum += v[i];
        vals[i]=sum;
    }
    sort(vals,vals+1+n);
    sum=0;
    mp[norma(0)] = n + 1;
    for(int i = n; i >= 1; i--)
    {
        sum += v[i];
        bl[i][0] = mindr;
        if(mp[norma(sum)] != 0)
            mindr = min(mindr, mp[norma(sum)] - 1LL);
        mp[norma(sum)] = i;
        //cout<<i<<" "<<mindr<<'\n';
    }

    bl[0][0] = mindr;

    for(int j = 1; j < 3; j++)
        for(int i = 0; i <= n; i++)
        {
            int nod = i;
            for(int k = 1; k <= 80 && nod != n + 1; k++)
                nod = bl[nod][j - 1];
            bl[i][j] = nod;
        }

    cin>>q;
    for(int i = 1; i <= q; i++)
    {
        int a, b;
        cin>>a>>b;
        cout<<query(a - 1, b)<<'\n';
    }

    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6488 KB Output is correct
2 Correct 5 ms 6688 KB Output is correct
3 Correct 5 ms 6488 KB Output is correct
4 Correct 5 ms 6488 KB Output is correct
5 Correct 5 ms 6488 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 122 ms 9296 KB Output is correct
8 Correct 89 ms 9044 KB Output is correct
9 Correct 134 ms 9296 KB Output is correct
10 Correct 123 ms 9044 KB Output is correct
11 Correct 98 ms 9296 KB Output is correct
12 Correct 139 ms 9080 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6488 KB Output is correct
2 Correct 5 ms 6688 KB Output is correct
3 Correct 5 ms 6488 KB Output is correct
4 Correct 5 ms 6488 KB Output is correct
5 Correct 5 ms 6488 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 122 ms 9296 KB Output is correct
8 Correct 89 ms 9044 KB Output is correct
9 Correct 134 ms 9296 KB Output is correct
10 Correct 123 ms 9044 KB Output is correct
11 Correct 98 ms 9296 KB Output is correct
12 Correct 139 ms 9080 KB Output is correct
13 Correct 574 ms 13460 KB Output is correct
14 Correct 420 ms 13136 KB Output is correct
15 Correct 691 ms 20464 KB Output is correct
16 Correct 584 ms 19452 KB Output is correct
17 Correct 464 ms 20352 KB Output is correct
18 Correct 692 ms 20472 KB Output is correct