Submission #1149483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149483		monkey133	Index (COCI21_index)	C++20	110 / 110	1150 ms	45600 KiB

index

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct wavelet_tree { //1 indexed
    int s, e, m;
    wavelet_tree * left, * right;
    vector < int > b;
 
    wavelet_tree(vector < int > vect, int x, int y) {
        s = x, e = y, m = (s + e) / 2;
        if (s == e || vect.empty()) return;
        b.resize(vect.size() + 1, 0);
        vector < int > l, r;
        for (int i = 0; i < vect.size(); ++i) {
            b[i + 1] = b[i];
            if (vect[i] <= m) ++b[i + 1], l.pb(vect[i]);
            else r.pb(vect[i]);
        }
        left = new wavelet_tree(l, s, m);
        right = new wavelet_tree(r, m + 1, e);
}
//kth smallest element in [l, r]
    int kth(int l, int r, int k) { 
        if (l > r) return 0;
        if (s == e) return s;
        if (k <= b[r] - b[l - 1]) return left -> kth(b[l - 1] + 1, b[r], k);
        return right -> kth(l - b[l - 1], r - b[r], k - (b[r] - b[l - 1]));
}
//count of nos in [l, r] Less than or equal to k
    int lte(int l, int r, int k) { 
    if (l > r || k < s) return 0;
        if (e <= k) return r - l + 1;
        return left -> lte(b[l - 1] + 1, b[r], k) + right -> lte(l - b[l - 1], r - b[r], k);
}
//count of nos in [l, r] More than or equal to k
    int mte(int l, int r, int k) {
        if (l > r || k > e) return 0;
        if (k <= s) return r - l + 1;
        return left -> mte(b[l - 1] + 1, b[r], k) + right -> mte(l - b[l - 1], r - b[r], k);
}
// count of nos in [l, r] equal to k
    int count(int l, int r, int k) {
        if (l > r || s > k || e < k) return 0;
        if (s == e) return r - l + 1;
        if (k <= m) return left -> count(b[l - 1] + 1, b[r], k);
        return right -> count(l - b[l - 1], r - b[r], k);
    }
}* wt;



int main()
{
	ll n,q;
	cin >> n >> q;
	vector<int> arr(n);
	for (ll i=0; i<n; ++i) cin >> arr[i];
	wt = new wavelet_tree(arr, 1, n);
	while (q--)
	{
		ll l, r;
		cin >> l >> r;
		ll lo = 0, hi = r-l + 1;
		while (lo!=hi)
		{
			ll mid = (lo + hi+1) >> 1;
			if (wt->mte(l, r, mid) >= mid) lo = mid;
			else hi = mid-1;
		}
		cout << lo << endl;
	}
	return 0;
}

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