oj.uz

Submission #955201

# Submission time Handle Problem Language Result Execution time Memory
955201 2024-03-29T16:24:02 Z shezitt Index (COCI21_index) C++14
110 / 110
 1596 ms 136320 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];
    }
 
    version[0] = new Node();
    init(version[0], 0, N);
 
    fore(i, 0, n){
        version[i+1] = new Node();
        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;
 
    }
 
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13404 KB Output is correct
2 Correct 17 ms 13404 KB Output is correct
3 Correct 17 ms 13404 KB Output is correct
4 Correct 16 ms 13344 KB Output is correct
5 Correct 17 ms 13488 KB Output is correct
6 Correct 18 ms 13400 KB Output is correct
7 Correct 18 ms 13404 KB Output is correct
8 Correct 16 ms 13400 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 16 ms 13404 KB Output is correct
11 Correct 354 ms 43552 KB Output is correct
12 Correct 309 ms 43604 KB Output is correct
13 Correct 311 ms 43604 KB Output is correct
14 Correct 336 ms 43736 KB Output is correct
15 Correct 343 ms 43604 KB Output is correct
16 Correct 319 ms 43668 KB Output is correct
17 Correct 336 ms 43460 KB Output is correct
18 Correct 333 ms 43672 KB Output is correct
19 Correct 335 ms 43676 KB Output is correct
20 Correct 322 ms 43492 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13404 KB Output is correct
2 Correct 17 ms 13404 KB Output is correct
3 Correct 17 ms 13404 KB Output is correct
4 Correct 16 ms 13344 KB Output is correct
5 Correct 17 ms 13488 KB Output is correct
6 Correct 18 ms 13400 KB Output is correct
7 Correct 18 ms 13404 KB Output is correct
8 Correct 16 ms 13400 KB Output is correct
9 Correct 16 ms 13400 KB Output is correct
10 Correct 16 ms 13404 KB Output is correct
11 Correct 354 ms 43552 KB Output is correct
12 Correct 309 ms 43604 KB Output is correct
13 Correct 311 ms 43604 KB Output is correct
14 Correct 336 ms 43736 KB Output is correct
15 Correct 343 ms 43604 KB Output is correct
16 Correct 319 ms 43668 KB Output is correct
17 Correct 336 ms 43460 KB Output is correct
18 Correct 333 ms 43672 KB Output is correct
19 Correct 335 ms 43676 KB Output is correct
20 Correct 322 ms 43492 KB Output is correct
21 Correct 1584 ms 136072 KB Output is correct
22 Correct 1552 ms 135984 KB Output is correct
23 Correct 1522 ms 136040 KB Output is correct
24 Correct 1585 ms 136052 KB Output is correct
25 Correct 1560 ms 135840 KB Output is correct
26 Correct 1527 ms 135860 KB Output is correct
27 Correct 1516 ms 136056 KB Output is correct
28 Correct 1596 ms 135660 KB Output is correct
29 Correct 1560 ms 136320 KB Output is correct
30 Correct 1566 ms 136020 KB Output is correct