oj.uz

Submission #892083

# Submission time Handle Problem Language Result Execution time Memory
892083 2023-12-24T18:40:16 Z kh0i Index (COCI21_index) C++17
110 / 110
 1687 ms 11012 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 4104 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 2 ms 3928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 4104 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 2 ms 3928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 200 ms 5312 KB Output is correct
12 Correct 199 ms 5160 KB Output is correct
13 Correct 207 ms 5312 KB Output is correct
14 Correct 199 ms 5200 KB Output is correct
15 Correct 202 ms 5200 KB Output is correct
16 Correct 203 ms 5412 KB Output is correct
17 Correct 205 ms 5312 KB Output is correct
18 Correct 200 ms 5308 KB Output is correct
19 Correct 203 ms 5328 KB Output is correct
20 Correct 201 ms 5200 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 4104 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 2 ms 3932 KB Output is correct
6 Correct 2 ms 3932 KB Output is correct
7 Correct 2 ms 3932 KB Output is correct
8 Correct 2 ms 3928 KB Output is correct
9 Correct 2 ms 3932 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 200 ms 5312 KB Output is correct
12 Correct 199 ms 5160 KB Output is correct
13 Correct 207 ms 5312 KB Output is correct
14 Correct 199 ms 5200 KB Output is correct
15 Correct 202 ms 5200 KB Output is correct
16 Correct 203 ms 5412 KB Output is correct
17 Correct 205 ms 5312 KB Output is correct
18 Correct 200 ms 5308 KB Output is correct
19 Correct 203 ms 5328 KB Output is correct
20 Correct 201 ms 5200 KB Output is correct
21 Correct 1641 ms 10860 KB Output is correct
22 Correct 1637 ms 10648 KB Output is correct
23 Correct 1624 ms 10764 KB Output is correct
24 Correct 1592 ms 10836 KB Output is correct
25 Correct 1682 ms 10652 KB Output is correct
26 Correct 1687 ms 10648 KB Output is correct
27 Correct 1629 ms 10644 KB Output is correct
28 Correct 1639 ms 10640 KB Output is correct
29 Correct 1645 ms 11012 KB Output is correct
30 Correct 1614 ms 10644 KB Output is correct