oj.uz

Submission #955172

# Submission time Handle Problem Language Result Execution time Memory
955172 2024-03-29T14:46:48 Z shezitt Index (COCI21_index) C++17
110 / 110
 1645 ms 140076 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

using namespace std;

using ll = long long;
#define int ll
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define raya cerr << "==================" << endl;

#define fore(i, a, b) for(int i=a; i<b; ++i)

const int N = 2e5+5;

int p[N], n, q;

int mp[N];

struct Node {
    Node *left, *right;
    int val;

    Node() {
        left = nullptr;
        right = nullptr;
        val = 0;
    }

};

int arr[N];

Node* version[N];

void init(Node *cur, int tl, int tr){
    if(tl == tr){
        cur->val = arr[tl];
        return;
    }

    int tm = (tl + tr) / 2;

    cur->left = new Node();
    cur->right = new Node();

    init(cur->left, tl, tm);
    init(cur->right, tm+1, tr);

    cur->val = cur->left->val + cur->right->val;

}

void update(Node *cur, Node *prev, int tl, int tr, int idx, int val){
    if(tl == tr){
        arr[tl] = val;
        cur->val = val;
        return;
    }

    int tm = (tl + tr) / 2;

    if(idx <= tm){
        cur->left = new Node();
        cur->right = prev->right;
        update(cur->left, prev->left, tl, tm, idx, val);
    } else {
        cur->left = prev->left;
        cur->right = new Node();
        update(cur->right, prev->right, tm+1, tr, idx, val);
    }

    cur->val = cur->left->val + cur->right->val;

}

void update(Node *cur, Node *prev, int idx, int val){
    update(cur, prev, 0, N-1, idx, val);
}

int query(Node *cur, int tl, int tr, int l, int r){
    if(l <= tl && tr <= r){
        return cur->val;
    }

    if(r < tl or tr < l){
        return 0;
    }

    int tm = (tl + tr) / 2;

    int p1 = query(cur->left, tl, tm, l, r);
    int p2 = query(cur->right, tm+1, tr, l, r);

    return p1 + p2;

}

int query(Node *cur, int l, int r){
    return query(cur, 0, N-1, l, r);
}

signed main(){
    cin >> n >> q;

    fore(i, 0, n){
        cin >> p[i];
    }

    // vector<int> sorted;
    // sorted.insert(sorted.begin(), p, p+n);

    // sort(all(sorted));
    // sorted.erase(unique(all(sorted)), sorted.end());

    // fore(i, 0, sz(sorted)){
    //     mp[sorted[i]] = i;
    // }

    version[0] = new Node();
    init(version[0], 0, N);

    fore(i, 0, n){
        version[i+1] = new Node();
        // int key = mp[p[i]];
        int prevVal = query(version[i], p[i], p[i]);
        update(version[i+1], version[i], p[i], prevVal + 1);
    }

    fore(i, 0, q){
        int l, r;
        cin >> l >> r;

        int low = 1, high = N;
        int res = -1;

        while(low <= high){
            int mid = low + (high - low) / 2;

            int cnt = query(version[r], mid, N-1) - query(version[l-1], mid, N-1);

            if(cnt >= mid){
                res = mid;
                low = mid+1;
            } else {
                high = mid-1;
            }

        }

        cout << res << endl;

        // vector<int> tmp;
        // tmp.insert(tmp.begin(), p+l-1, p+r);

        // sort(tmp.rbegin(), tmp.rend());

        // int low = 1, high = sz(tmp);
        // int res = -1;
        // while(low <= high){
        //     int mid = (low + high) / 2;
        //     if(tmp[mid-1] >= mid){
        //         res = mid;
        //         low = mid+1;
        //     } else {
        //         high = mid-1;
        //     }
        // }
        // assert( res > -1);
        // cout << res << endl;

    }

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13400 KB Output is correct
2 Correct 17 ms 13404 KB Output is correct
3 Correct 16 ms 13500 KB Output is correct
4 Correct 17 ms 13404 KB Output is correct
5 Correct 16 ms 13404 KB Output is correct
6 Correct 17 ms 13404 KB Output is correct
7 Correct 16 ms 13404 KB Output is correct
8 Correct 17 ms 13436 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 18 ms 13656 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13400 KB Output is correct
2 Correct 17 ms 13404 KB Output is correct
3 Correct 16 ms 13500 KB Output is correct
4 Correct 17 ms 13404 KB Output is correct
5 Correct 16 ms 13404 KB Output is correct
6 Correct 17 ms 13404 KB Output is correct
7 Correct 16 ms 13404 KB Output is correct
8 Correct 17 ms 13436 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 18 ms 13656 KB Output is correct
11 Correct 316 ms 43816 KB Output is correct
12 Correct 326 ms 44648 KB Output is correct
13 Correct 341 ms 44368 KB Output is correct
14 Correct 309 ms 44308 KB Output is correct
15 Correct 316 ms 44680 KB Output is correct
16 Correct 311 ms 44444 KB Output is correct
17 Correct 329 ms 44384 KB Output is correct
18 Correct 340 ms 44488 KB Output is correct
19 Correct 326 ms 44600 KB Output is correct
20 Correct 340 ms 44372 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 13400 KB Output is correct
2 Correct 17 ms 13404 KB Output is correct
3 Correct 16 ms 13500 KB Output is correct
4 Correct 17 ms 13404 KB Output is correct
5 Correct 16 ms 13404 KB Output is correct
6 Correct 17 ms 13404 KB Output is correct
7 Correct 16 ms 13404 KB Output is correct
8 Correct 17 ms 13436 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 18 ms 13656 KB Output is correct
11 Correct 316 ms 43816 KB Output is correct
12 Correct 326 ms 44648 KB Output is correct
13 Correct 341 ms 44368 KB Output is correct
14 Correct 309 ms 44308 KB Output is correct
15 Correct 316 ms 44680 KB Output is correct
16 Correct 311 ms 44444 KB Output is correct
17 Correct 329 ms 44384 KB Output is correct
18 Correct 340 ms 44488 KB Output is correct
19 Correct 326 ms 44600 KB Output is correct
20 Correct 340 ms 44372 KB Output is correct
21 Correct 1562 ms 139620 KB Output is correct
22 Correct 1524 ms 139856 KB Output is correct
23 Correct 1561 ms 139720 KB Output is correct
24 Correct 1534 ms 139628 KB Output is correct
25 Correct 1525 ms 139708 KB Output is correct
26 Correct 1533 ms 139648 KB Output is correct
27 Correct 1645 ms 139332 KB Output is correct
28 Correct 1535 ms 140076 KB Output is correct
29 Correct 1577 ms 139896 KB Output is correct
30 Correct 1550 ms 139460 KB Output is correct