oj.uz

Submission #1055382

# Submission time Handle Problem Language Result Execution time Memory
1055382 2024-08-12T18:33:36 Z fryingduc Index (COCI21_index) C++17
110 / 110
 672 ms 151700 KB 
/**
 *	author: fryingduc
 *	created:03.09.2023 20:39:40
**/
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)     
#endif

/* #define int long long */

const int maxn = 2e5+5;
const int off = (1 << 18);
struct Node{
    int x;
    Node *l, *r;
    Node (int _x = 0, Node *_l = 0, Node *_r = 0){
        x = _x;
        l = _l;
        r = _r;
    }
};
Node* liu(){
    Node *x = new Node();
    x->r = x->l = x;
    return x;
}
Node *tmp;
Node *tree[maxn];
Node *update(Node *ind, int l, int r, int x){
    if(x < l || x > r) return ind;
    if(l == r){
        return new Node(ind->x + 1, liu(), liu()); 
    }
    int mid = (l + r) / 2;
    Node *left = update(ind->l, l, mid, x);
    Node *right = update(ind->r, mid + 1, r, x);
    return new Node(left->x + right->x, left, right);
}
int get(Node *ind, Node *prev, int l, int r, int x){
    if(x > r || l >= maxn) return 0;
    if(l >= x) return ind->x - prev->x;

    int mid = (l + r) / 2;
    return get(ind->l, prev->l, l, mid, x) + get(ind->r, prev->r, mid + 1, r, x);
}
int get(Node *ind, Node *prev, int x){
    return get(ind, prev, 1, off, x);
}
int n, q, a[maxn];
void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        tmp = liu();
        if(i > 1) tmp = tree[i - 1];
        tree[i] = update(tmp, 1, off, a[i]);
    }
    while(q--){
        int el, er; cin >> el >> er;
        int l = 0, r = maxn, res = 0;
        tmp = liu();
        if(el > 1) tmp = tree[el - 1];
        while(l <= r){
            int mid = (l + r) / 2;
            if(get(tree[er], tmp, mid) >= mid){
                l = mid + 1;
                res = mid;
            }
            else r = mid - 1;
        }
        cout << res << '\n';

    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int test = 1;
    /* cin >> test; */
    for(int i = 1; i <= test; i++){
        /* cout << "Case " << "#" << i << ": "; */
        solve();
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3220 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3220 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 119 ms 39764 KB Output is correct
12 Correct 116 ms 39624 KB Output is correct
13 Correct 120 ms 39680 KB Output is correct
14 Correct 134 ms 39768 KB Output is correct
15 Correct 113 ms 39760 KB Output is correct
16 Correct 117 ms 39760 KB Output is correct
17 Correct 114 ms 39764 KB Output is correct
18 Correct 151 ms 39764 KB Output is correct
19 Correct 118 ms 39652 KB Output is correct
20 Correct 133 ms 39548 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3220 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 119 ms 39764 KB Output is correct
12 Correct 116 ms 39624 KB Output is correct
13 Correct 120 ms 39680 KB Output is correct
14 Correct 134 ms 39768 KB Output is correct
15 Correct 113 ms 39760 KB Output is correct
16 Correct 117 ms 39760 KB Output is correct
17 Correct 114 ms 39764 KB Output is correct
18 Correct 151 ms 39764 KB Output is correct
19 Correct 118 ms 39652 KB Output is correct
20 Correct 133 ms 39548 KB Output is correct
21 Correct 634 ms 151636 KB Output is correct
22 Correct 632 ms 151632 KB Output is correct
23 Correct 631 ms 151692 KB Output is correct
24 Correct 643 ms 151700 KB Output is correct
25 Correct 636 ms 151636 KB Output is correct
26 Correct 660 ms 151484 KB Output is correct
27 Correct 672 ms 151544 KB Output is correct
28 Correct 659 ms 151560 KB Output is correct
29 Correct 643 ms 151520 KB Output is correct
30 Correct 652 ms 151604 KB Output is correct