Submission #1272255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272255		nerrrmin	Index (COCI21_index)	C++20	60 / 110	2594 ms	27984 KiB

index

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int maxn = 2e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct persistent_sgt
{
    struct node
    {
        int lt, rt, val;
        node(int _lt, int _rt, int _val)
        {
            lt = _lt;
            rt = _rt;
            val = _val;
        }
    };
    vector < node > t;
    int tmr, n;
    int build(int l, int r, vector < int > a)
    {
        if(l == r)
        {
            t.pb(node(-1, -1, a[l]));
            return tmr ++;
        }
        int mid = (l + r)/2;
        int onl = build(l, mid, a);
        int onr = build(mid+1, r, a);
        t.pb(node(onl, onr, a[l]));
        return tmr ++;
    }
    int do_build(int sz, vector < int > a)
    {
        tmr = 0;
        n = sz;
        return build(1, n, a);
    }
    int update(int i, int l, int r, int upd_pos, int upd_val)
    {
        if(l == r)
        {
            t.pb(node(-1, -1, upd_val));
            return tmr ++;
        }
        int mid = (l + r)/2;
        int onl = t[i].lt, onr = t[i].rt;
        if(upd_pos <= mid)onl = update(t[i].lt, l, mid, upd_pos, upd_val);
        else onr = update(t[i].rt, mid+1, r, upd_pos, upd_val);
        t.pb(node(onl, onr, t[onl].val + t[onr].val));
        return tmr ++;
    }
    int do_update(int root, int upd_pos, int upd_val)
    {
        return update(root, 1, n, upd_pos, upd_val);
    }
    int query(int i, int l, int r, int ql, int qr)
    {
        if(i == -1)return 0;
        if(qr < l || ql > r)return 0;
        if(ql <= l && r <= qr)return t[i].val;

        int mid = (l + r)/2;
        return query(t[i].lt, l, mid, ql, qr) + query(t[i].rt, mid+1, r, ql, qr);
    }
    int do_query(int root, int ql, int qr)
    {
        return query(root, 1, n, ql, qr);
    }
};
persistent_sgt s;
int n, q;
int p[maxn];
vector < int > pos[maxn];
int total, root[maxn], dp[maxn], mp[maxn], is_mp[maxn];
int main()
{
    speed();
    cin >> n >> q;
    vector < int > v;
    vector < int > init;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> p[i];
        init.pb(0);
       if(pos[p[i]].size() == 0)v.pb(p[i]);
       pos[p[i]].pb(i);
    }
    init.pb(0);
    total = v.size();
    sort(v.begin(), v.end());
    int last_root = s.do_build(n, init);
    /// shte sme na posledniq

    for (int i = v.size()-1; i >= 0; -- i)
    {
        int x = v[i];
        mp[x] = i;
        is_mp[x] = 1;
        for (auto index: pos[x])
        {
            int curr_root = s.do_update(last_root, index, 1);
            last_root = curr_root;
        }
        root[i] = last_root;
    }
    int ptr = -1;
    for(int i = 200000; i>= 0; -- i)
    {
        if(is_mp[i])ptr = mp[i];
        dp[i] = ptr;
    }
    while(q --)
    {
        int ql, qr;
        cin >> ql >> qr;
        int l = 0, r = 200000, mid, ans = 0;
        while(l <= r)
        {
            mid = (l + r)/2;

            int sum = 0;
            if(dp[mid] != -1)sum = s.do_query(root[dp[mid]], ql, qr);

            if(sum >= mid)
            {
            l = mid + 1;
                ans = mid;
            }
            else r = mid - 1;
        }
        cout << ans << endl;
    }
    return 0;
}

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