Submission #1299475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299475		DangKhoizzzz	Index (COCI21_index)	C++20	110 / 110	1078 ms	133500 KiB

index

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;
const int maxn = 2e5 + 7;

int n;
struct PST
{
    struct node
    {
        int sum;
        node *l_child; node *r_child;
        node(node *x)
        {
            sum = x->sum;
            l_child = x->l_child;
            r_child = x->r_child;
        }
        node(int x)
        {
            sum = x;
            l_child = r_child = NULL;
        }
        node(node *lnode , node *rnode)
        {
            sum = lnode->sum + rnode->sum;
            l_child = lnode;
            r_child = rnode;
        }
    } *root[maxn];

    node *build(int l , int r)
    {
        if(l == r) return new node(0);
        int mid = (l+r)>>1;
        return new node(node(build(l , mid) , build(mid+1 , r)));
    }
    node *update(node *id , int l , int r , int pos , int val)
    {
        if(l == r)
        {
            node *cur = new node(id);
            cur->sum += val;
            return cur;
        }
        int mid = (l+r)>>1;
        if(pos <= mid)
        {
            return new node(update(id->l_child , l , mid , pos , val) , id->r_child);
        }
        else
        {
            return new node(id->l_child , update(id->r_child , mid+1 , r , pos , val));
        }
    }
    int get(node *id , int l , int r , int u , int v)
    {
        if(r < u || l > v) return 0;
        if(u <= l && r <= v) return id->sum;
        int mid = (l+r)>>1;
        return get(id->l_child , l , mid , u , v) + get(id->r_child , mid+1 , r , u , v);
    }
    void add(int event)
    {
        root[event] = root[event-1];
    }
    void upd(int event , int pos , int val)
    {
        root[event] = update(root[event] , 1 , n , pos , val);
    }
    int gt(int event , int l , int r)
    {
        return get(root[event] , 1 , n , l , r);
    }
} pst;

int p[maxn] , q;

void solve()
{
    cin >> n >> q;
    pst.root[0] = pst.build(1 , n);
    for(int i = 1; i <= n; i++)
    {
        cin >> p[i];
        pst.add(i);
        pst.upd(i , p[i] , 1);
    }
    while(q--)
    {
        int l , r; cin >> l >> r;
        int lo = 1 , hi = (r - l + 1) , ans = 1;
        while(lo <= hi)
        {
            int mid = (lo + hi)>>1;
            int chk = pst.gt(r , mid , n) - pst.gt(l-1 , mid , n);
            if(chk >= mid)
            {
                ans = mid;
                lo = mid + 1;
            }
            else hi = mid - 1;
        }
        cout << ans << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50