Submission #1135440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135440		DangKhoizzzz	Index (COCI21_index)	C++20	110 / 110	2037 ms	19100 KiB

index

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

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 2e5 + 7;

int n , q , a[maxn];
vector <int> bit[maxn];

void update(int id , int val)
{
    int idx = id;
    while(idx <= n)
    {
        bit[idx].push_back(val);
        idx += (idx & (-idx));
    }
}

int getp(int p , int val)
{
    int idx = p;
    int res = 0;

    while(idx > 0)
    {
        res += (int)(lower_bound(bit[idx].begin() , bit[idx].end() , val) - bit[idx].begin());
        idx -= (idx & (-idx));
    }
    return res;
}

int get_ask(int l , int r , int val)
{
    return (r - l + 1) - (getp(r , val) - getp(l-1 , val));
}


void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) update(i , a[i]);

    for(int i = 1; i <= n; i++)
    {
        sort(bit[i].begin() , bit[i].end());
    }

    while(q--)
    {
        int L , R , H = -1; cin >> L >> R;
        int l = 1 , r = (R - L + 1);
        while(l <= r)
        {
            int mid = (l + r)/2;
            if(get_ask(L , R , mid) >= mid)
            {
                H = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        cout << H << '\n';
    }
}

int 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