oj.uz

Submission #751302

# Submission time Handle Problem Language Result Execution time Memory
751302 2023-05-31T11:12:59 Z sofija6 Index (COCI21_index) C++14
60 / 110
 391 ms 95448 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
#define MAXV 2000010
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 6992 KB Output is correct
2 Correct 7 ms 7084 KB Output is correct
3 Correct 7 ms 6996 KB Output is correct
4 Correct 7 ms 6996 KB Output is correct
5 Correct 8 ms 6996 KB Output is correct
6 Correct 8 ms 6996 KB Output is correct
7 Correct 7 ms 6996 KB Output is correct
8 Correct 9 ms 6996 KB Output is correct
9 Correct 7 ms 7100 KB Output is correct
10 Correct 8 ms 6996 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6992 KB Output is correct
2 Correct 7 ms 7084 KB Output is correct
3 Correct 7 ms 6996 KB Output is correct
4 Correct 7 ms 6996 KB Output is correct
5 Correct 8 ms 6996 KB Output is correct
6 Correct 8 ms 6996 KB Output is correct
7 Correct 7 ms 6996 KB Output is correct
8 Correct 9 ms 6996 KB Output is correct
9 Correct 7 ms 7100 KB Output is correct
10 Correct 8 ms 6996 KB Output is correct
11 Correct 362 ms 30352 KB Output is correct
12 Correct 366 ms 30384 KB Output is correct
13 Correct 338 ms 30352 KB Output is correct
14 Correct 361 ms 30408 KB Output is correct
15 Correct 349 ms 30412 KB Output is correct
16 Correct 339 ms 30408 KB Output is correct
17 Correct 354 ms 30372 KB Output is correct
18 Correct 391 ms 30380 KB Output is correct
19 Correct 375 ms 30460 KB Output is correct
20 Correct 373 ms 30484 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6992 KB Output is correct
2 Correct 7 ms 7084 KB Output is correct
3 Correct 7 ms 6996 KB Output is correct
4 Correct 7 ms 6996 KB Output is correct
5 Correct 8 ms 6996 KB Output is correct
6 Correct 8 ms 6996 KB Output is correct
7 Correct 7 ms 6996 KB Output is correct
8 Correct 9 ms 6996 KB Output is correct
9 Correct 7 ms 7100 KB Output is correct
10 Correct 8 ms 6996 KB Output is correct
11 Correct 362 ms 30352 KB Output is correct
12 Correct 366 ms 30384 KB Output is correct
13 Correct 338 ms 30352 KB Output is correct
14 Correct 361 ms 30408 KB Output is correct
15 Correct 349 ms 30412 KB Output is correct
16 Correct 339 ms 30408 KB Output is correct
17 Correct 354 ms 30372 KB Output is correct
18 Correct 391 ms 30380 KB Output is correct
19 Correct 375 ms 30460 KB Output is correct
20 Correct 373 ms 30484 KB Output is correct
21 Runtime error 130 ms 95448 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -