oj.uz

Submission #751306

# Submission time Handle Problem Language Result Execution time Memory
751306 2023-05-31T11:14:04 Z sofija6 Index (COCI21_index) C++14
110 / 110
 2405 ms 53964 KB 
#include <bits/stdc++.h>
#define ll int
#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;
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:77:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         cout << ans << "\n";
      |                        ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3668 KB Output is correct
2 Correct 6 ms 3720 KB Output is correct
3 Correct 6 ms 3668 KB Output is correct
4 Correct 5 ms 3668 KB Output is correct
5 Correct 6 ms 3668 KB Output is correct
6 Correct 6 ms 3668 KB Output is correct
7 Correct 5 ms 3668 KB Output is correct
8 Correct 6 ms 3668 KB Output is correct
9 Correct 6 ms 3720 KB Output is correct
10 Correct 5 ms 3668 KB Output is correct
11 Correct 324 ms 15104 KB Output is correct
12 Correct 322 ms 15120 KB Output is correct
13 Correct 318 ms 15076 KB Output is correct
14 Correct 309 ms 15232 KB Output is correct
15 Correct 324 ms 15176 KB Output is correct
16 Correct 309 ms 15108 KB Output is correct
17 Correct 333 ms 15132 KB Output is correct
18 Correct 318 ms 15120 KB Output is correct
19 Correct 316 ms 15112 KB Output is correct
20 Correct 307 ms 15112 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3668 KB Output is correct
2 Correct 6 ms 3720 KB Output is correct
3 Correct 6 ms 3668 KB Output is correct
4 Correct 5 ms 3668 KB Output is correct
5 Correct 6 ms 3668 KB Output is correct
6 Correct 6 ms 3668 KB Output is correct
7 Correct 5 ms 3668 KB Output is correct
8 Correct 6 ms 3668 KB Output is correct
9 Correct 6 ms 3720 KB Output is correct
10 Correct 5 ms 3668 KB Output is correct
11 Correct 324 ms 15104 KB Output is correct
12 Correct 322 ms 15120 KB Output is correct
13 Correct 318 ms 15076 KB Output is correct
14 Correct 309 ms 15232 KB Output is correct
15 Correct 324 ms 15176 KB Output is correct
16 Correct 309 ms 15108 KB Output is correct
17 Correct 333 ms 15132 KB Output is correct
18 Correct 318 ms 15120 KB Output is correct
19 Correct 316 ms 15112 KB Output is correct
20 Correct 307 ms 15112 KB Output is correct
21 Correct 2171 ms 50228 KB Output is correct
22 Correct 2183 ms 53904 KB Output is correct
23 Correct 2209 ms 53964 KB Output is correct
24 Correct 2291 ms 53892 KB Output is correct
25 Correct 2186 ms 53816 KB Output is correct
26 Correct 2257 ms 53820 KB Output is correct
27 Correct 2299 ms 53924 KB Output is correct
28 Correct 2197 ms 53808 KB Output is correct
29 Correct 2156 ms 53772 KB Output is correct
30 Correct 2405 ms 53692 KB Output is correct