oj.uz

Submission #751308

# Submission time Handle Problem Language Result Execution time Memory
751308 2023-05-31T11:16:06 Z sofija6 Index (COCI21_index) C++14
110 / 110
 2425 ms 50252 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 5 ms 3668 KB Output is correct
2 Correct 5 ms 3668 KB Output is correct
3 Correct 6 ms 3668 KB Output is correct
4 Correct 6 ms 3720 KB Output is correct
5 Correct 6 ms 3728 KB Output is correct
6 Correct 8 ms 3668 KB Output is correct
7 Correct 6 ms 3668 KB Output is correct
8 Correct 5 ms 3668 KB Output is correct
9 Correct 6 ms 3668 KB Output is correct
10 Correct 6 ms 3668 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3668 KB Output is correct
2 Correct 5 ms 3668 KB Output is correct
3 Correct 6 ms 3668 KB Output is correct
4 Correct 6 ms 3720 KB Output is correct
5 Correct 6 ms 3728 KB Output is correct
6 Correct 8 ms 3668 KB Output is correct
7 Correct 6 ms 3668 KB Output is correct
8 Correct 5 ms 3668 KB Output is correct
9 Correct 6 ms 3668 KB Output is correct
10 Correct 6 ms 3668 KB Output is correct
11 Correct 330 ms 15224 KB Output is correct
12 Correct 369 ms 15144 KB Output is correct
13 Correct 302 ms 15116 KB Output is correct
14 Correct 331 ms 15096 KB Output is correct
15 Correct 321 ms 15116 KB Output is correct
16 Correct 321 ms 15160 KB Output is correct
17 Correct 307 ms 15088 KB Output is correct
18 Correct 292 ms 15352 KB Output is correct
19 Correct 316 ms 15108 KB Output is correct
20 Correct 303 ms 15188 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3668 KB Output is correct
2 Correct 5 ms 3668 KB Output is correct
3 Correct 6 ms 3668 KB Output is correct
4 Correct 6 ms 3720 KB Output is correct
5 Correct 6 ms 3728 KB Output is correct
6 Correct 8 ms 3668 KB Output is correct
7 Correct 6 ms 3668 KB Output is correct
8 Correct 5 ms 3668 KB Output is correct
9 Correct 6 ms 3668 KB Output is correct
10 Correct 6 ms 3668 KB Output is correct
11 Correct 330 ms 15224 KB Output is correct
12 Correct 369 ms 15144 KB Output is correct
13 Correct 302 ms 15116 KB Output is correct
14 Correct 331 ms 15096 KB Output is correct
15 Correct 321 ms 15116 KB Output is correct
16 Correct 321 ms 15160 KB Output is correct
17 Correct 307 ms 15088 KB Output is correct
18 Correct 292 ms 15352 KB Output is correct
19 Correct 316 ms 15108 KB Output is correct
20 Correct 303 ms 15188 KB Output is correct
21 Correct 2425 ms 50112 KB Output is correct
22 Correct 2305 ms 50116 KB Output is correct
23 Correct 2227 ms 50188 KB Output is correct
24 Correct 2177 ms 50072 KB Output is correct
25 Correct 2217 ms 50196 KB Output is correct
26 Correct 2153 ms 50252 KB Output is correct
27 Correct 2266 ms 50144 KB Output is correct
28 Correct 2174 ms 50092 KB Output is correct
29 Correct 2178 ms 50220 KB Output is correct
30 Correct 2054 ms 50008 KB Output is correct