oj.uz

Submission #751305

# Submission time Handle Problem Language Result Execution time Memory
751305 2023-05-31T11:13:26 Z sofija6 Index (COCI21_index) C++14
60 / 110
 2500 ms 100896 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
#define MAXV 5000010
using namespace std;
ll p[MAXN],root[MAXV],l[MAXV],r[MAXV],val[MAXV],ind=1;
void Init(ll node,ll lx,ll rx)
{
    if (lx==rx)
        return;
    l[node]=ind++;
    r[node]=ind++;
    ll mid=(lx+rx)/2;
    Init(l[node],lx,mid);
    Init(r[node],mid+1,rx);
}
void Update(ll node,ll pnode,ll lx,ll rx,ll pos,ll vall)
{
    if (lx==rx)
    {
        val[node]=val[pnode]+vall;
        return;
    }
    ll mid=(lx+rx)/2;
    if (pos<=mid)
    {
        l[node]=ind++;
        r[node]=r[pnode];
        Update(l[node],l[pnode],lx,mid,pos,vall);
    }
    else
    {
        l[node]=l[pnode];
        r[node]=ind++;
        Update(r[node],r[pnode],mid+1,rx,pos,vall);
    }
    val[node]=val[l[node]]+val[r[node]];
}
ll Calc(ll node,ll lx,ll rx,ll L,ll R)
{
    if (lx>R || rx<L)
        return 0;
    if (lx>=L && rx<=R)
        return val[node];
    ll mid=(lx+rx)/2;
    return Calc(l[node],lx,mid,L,R)+Calc(r[node],mid+1,rx,L,R);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,q,L,R;
    cin >> n >> q;
    for (ll i=1;i<=n;i++)
        cin >> p[i];
    root[0]=ind++;
    Init(root[0],1,MAXN);
    for (ll i=1;i<=n;i++)
    {
        root[i]=ind++;
        Update(root[i],root[i-1],1,MAXN,p[i],1);
    }
    while (q--)
    {
        cin >> L >> R;
        ll l=1,r=R-L+1,mid,ans;
        while (l<=r)
        {
            mid=(l+r)/2;
            if (Calc(root[R],1,MAXN,mid,MAXN)-Calc(root[L-1],1,MAXN,mid,MAXN)>=mid)
            {
                ans=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6996 KB Output is correct
2 Correct 7 ms 7084 KB Output is correct
3 Correct 6 ms 6996 KB Output is correct
4 Correct 6 ms 6996 KB Output is correct
5 Correct 6 ms 6996 KB Output is correct
6 Correct 6 ms 6996 KB Output is correct
7 Correct 6 ms 6996 KB Output is correct
8 Correct 7 ms 6996 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 6 ms 6996 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6996 KB Output is correct
2 Correct 7 ms 7084 KB Output is correct
3 Correct 6 ms 6996 KB Output is correct
4 Correct 6 ms 6996 KB Output is correct
5 Correct 6 ms 6996 KB Output is correct
6 Correct 6 ms 6996 KB Output is correct
7 Correct 6 ms 6996 KB Output is correct
8 Correct 7 ms 6996 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 6 ms 6996 KB Output is correct
11 Correct 347 ms 29620 KB Output is correct
12 Correct 352 ms 29592 KB Output is correct
13 Correct 389 ms 29592 KB Output is correct
14 Correct 357 ms 29644 KB Output is correct
15 Correct 397 ms 29588 KB Output is correct
16 Correct 373 ms 29552 KB Output is correct
17 Correct 399 ms 29620 KB Output is correct
18 Correct 431 ms 29588 KB Output is correct
19 Correct 347 ms 29644 KB Output is correct
20 Correct 384 ms 29684 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6996 KB Output is correct
2 Correct 7 ms 7084 KB Output is correct
3 Correct 6 ms 6996 KB Output is correct
4 Correct 6 ms 6996 KB Output is correct
5 Correct 6 ms 6996 KB Output is correct
6 Correct 6 ms 6996 KB Output is correct
7 Correct 6 ms 6996 KB Output is correct
8 Correct 7 ms 6996 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 6 ms 6996 KB Output is correct
11 Correct 347 ms 29620 KB Output is correct
12 Correct 352 ms 29592 KB Output is correct
13 Correct 389 ms 29592 KB Output is correct
14 Correct 357 ms 29644 KB Output is correct
15 Correct 397 ms 29588 KB Output is correct
16 Correct 373 ms 29552 KB Output is correct
17 Correct 399 ms 29620 KB Output is correct
18 Correct 431 ms 29588 KB Output is correct
19 Correct 347 ms 29644 KB Output is correct
20 Correct 384 ms 29684 KB Output is correct
21 Execution timed out 2542 ms 100896 KB Time limit exceeded
22 Halted 0 ms 0 KB -