Submission #892083

#	Time	Username	Problem	Language	Result	Execution time	Memory
892083		kh0i	Index (COCI21_index)	C++17	110 / 110	1687 ms	11012 KiB

index

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

#define F first
#define S second
#define sz(x) int((x).size())
using ll = long long; 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 2e5 + 3;

struct Query{
    int l, r, id;
} d[N];

struct Fenwick{
    #define gb(x) (x) & -(x)
    vector<ll> bit;
    int n;

    void init(int _n){
        bit.resize(_n + 4, 0);
        n = _n;
    }

    void upd(int x, ll val){
        while(x <= n){
            bit[x] += val;
            x += gb(x);
        }
    }

    ll get(int x){
        ll res = 0;
        while(x > 0){
            res += bit[x];
            x -= gb(x);
        }
        return res;
    }
} fen;

int n, q, p[N], ans, res[N];

void add(int x){
    fen.upd(p[x], 1);
    if(fen.get(N) - fen.get(ans) >= ans + 1)
        ++ans;
}

void del(int x){
    fen.upd(p[x], -1);
    if(fen.get(N) - fen.get(ans - 1) < ans)
        --ans;
}

void solve(){
    fen.init(N);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
        cin >> p[i];
    for(int i = 1; i <= q; ++i){
        cin >> d[i].l >> d[i].r;
        d[i].id = i;
    }
    int S = sqrt(n);
    sort(d + 1, d + q + 1, [S](const Query &A, const Query &B){
        return A.l / S != B.l / S ? A.l / S < B.l / S : A.r < B.r;
    });
    int l = 1, r = 0;
    for(int i = 1; i <= q; ++i){
        while(r < d[i].r) add(++r);
        while(r > d[i].r) del(r--);
        while(l < d[i].l) del(l++);
        while(l > d[i].l) add(--l);
        res[d[i].id] = ans;
    }
    for(int i = 1; i <= q; ++i)
        cout << res[i] << '\n';
}


int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

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