Submission #1152993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152993		_fractal	Index (COCI21_index)	C++20	110 / 110	1496 ms	120876 KiB

index

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 2e5 + 200;
const int M = 1e6;
const int inf = 2e9 + 3;
const ll INF = 1e18;

int n, q;
int a[N];
vector<int> t[N * 4], L[N * 4], R[N * 4];

void build(int v = 1, int tl = 1, int tr = n) {
    for (int i = tl; i <= tr; ++i) {
        t[v].push_back(a[i]);
    }
    sort(t[v].begin(), t[v].end());
    if (tl == tr) {
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    L[v].resize(sz(t[v]));
    R[v].resize(sz(t[v]));
    for (int i = 0; i < sz(t[v]); ++i) {
        L[v][i] = lower_bound(t[2 * v].begin(), t[2 * v].end(), t[v][i]) - t[2 * v].begin();
        R[v][i] = lower_bound(t[2 * v + 1].begin(), t[2 * v + 1].end(), t[v][i]) - t[2 * v + 1].begin();
    }
}

int get(int l, int r, int id, int v = 1, int tl = 1, int tr = n) {
    if (r < tl || tr < l || id == sz(t[v])) {
        return 0;
    }
    if (l <= tl && tr <= r) {
        return sz(t[v]) - id;
    }
    int tm = (tl + tr) / 2;
    return get(l, r, L[v][id], v * 2, tl, tm) + get(l, r, R[v][id], v * 2 + 1, tm + 1, tr);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build();
    for (int i = 1, l, r; i <= q; ++i) {
        cin >> l >> r;
        int tl = 1, tr = n, ansH = 1;
        while (tl <= tr) {
            int tm = (tl + tr) / 2;
            int h = tm;
            int id = lower_bound(t[1].begin(), t[1].end(), h) - t[1].begin();
            if (get(l, r, id) >= h) {
                ansH = h;
                tl = h + 1;
            }
            else {
                tr = h - 1;
            }
        }
        cout << ansH << '\n';
    }
}

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