oj.uz

Submission #862803

# Submission time Handle Problem Language Result Execution time Memory
862803 2023-10-19T04:19:56 Z deepaung Index (COCI21_index) C++14
110 / 110
 476 ms 202408 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define ll long long
#define pii pair<int, int>

using namespace std;

struct node {
    int val, left_idx, right_idx;
    node *l, *r;

    node(int val, int left_idx=0, int right_idx=0, node *l=NULL, node *r=NULL) : 
        val(val), left_idx(left_idx), right_idx(right_idx), l(l), r(r) {}

};

int n, w;
int p[200002];
node *seg[200002];

node* build(int l, int r) {
    if (l == r) return new node(0, l, l);

    int mid = (l + r) >> 1;
    node *resl = build(l, mid);
    node *resr = build(mid+1, r);

    return new node(
        resl->val + resr->val, 
        resl->left_idx, 
        resr->right_idx, 
        resl, 
        resr
    );
}

void upgrade(node *pre, node *cur, int i, int val, int l, int r) {
    if (l == r) {
        cur->val = pre->val + val;
        cur->left_idx = l;
        cur->right_idx = l;
        return;
    }

    int mid = (l + r) >> 1;
    if (i <= mid) {
        cur->l = new node(0);
        cur->r = pre->r;
        upgrade(pre->l, cur->l, i, val, l, mid);
    } else {
        cur->l = pre->l;
        cur->r = new node(0);
        upgrade(pre->r, cur->r, i, val, mid+1, r);
    }

    cur->val = cur->l->val + cur->r->val;
    cur->left_idx = cur->l->left_idx;
    cur->right_idx = cur->r->right_idx;
}

int findd(node *right, node *left, int add, int l, int r) {
    if (l == r) {
        return l;
    }

    int mid = (l + r) >> 1;

    int val = right->r->val - left->r->val + add;
    int left_idx = right->r->left_idx;

    if (left_idx <= val) {
        return findd(right->r, left->r, add, mid+1, r);
    } else {
        return findd(right->l, left->l, val, l, mid);
    }
}

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

    cin >> n >> w;
    for (int i = 1; i <= n; i++) cin >> p[i];

    seg[0] = build(1, 200000);
    // cout << seg[0]->r->left_idx << " " << seg[0]->l->right_idx << "\n";
    for (int i = 1; i <= n; i++) {
        seg[i] = new node(0);
        upgrade(seg[i-1], seg[i], p[i], 1, 1, 200000);
    }

    // cout << "hello\n";

    // return 0;

    int l, r;
    while (w--) {
        cin >> l >> r;
        int ans = findd(seg[r], seg[l-1], 0, 1, 200000);
        // for (auto it : res) cout << it << " "; cout << "\n";
        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22108 KB Output is correct
2 Correct 14 ms 22108 KB Output is correct
3 Correct 19 ms 22100 KB Output is correct
4 Correct 15 ms 22108 KB Output is correct
5 Correct 14 ms 22080 KB Output is correct
6 Correct 14 ms 22108 KB Output is correct
7 Correct 14 ms 22108 KB Output is correct
8 Correct 15 ms 22164 KB Output is correct
9 Correct 16 ms 21988 KB Output is correct
10 Correct 15 ms 21976 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22108 KB Output is correct
2 Correct 14 ms 22108 KB Output is correct
3 Correct 19 ms 22100 KB Output is correct
4 Correct 15 ms 22108 KB Output is correct
5 Correct 14 ms 22080 KB Output is correct
6 Correct 14 ms 22108 KB Output is correct
7 Correct 14 ms 22108 KB Output is correct
8 Correct 15 ms 22164 KB Output is correct
9 Correct 16 ms 21988 KB Output is correct
10 Correct 15 ms 21976 KB Output is correct
11 Correct 110 ms 66272 KB Output is correct
12 Correct 95 ms 66680 KB Output is correct
13 Correct 116 ms 66468 KB Output is correct
14 Correct 87 ms 66384 KB Output is correct
15 Correct 89 ms 66388 KB Output is correct
16 Correct 98 ms 66244 KB Output is correct
17 Correct 87 ms 66392 KB Output is correct
18 Correct 95 ms 66380 KB Output is correct
19 Correct 87 ms 66384 KB Output is correct
20 Correct 86 ms 66396 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22108 KB Output is correct
2 Correct 14 ms 22108 KB Output is correct
3 Correct 19 ms 22100 KB Output is correct
4 Correct 15 ms 22108 KB Output is correct
5 Correct 14 ms 22080 KB Output is correct
6 Correct 14 ms 22108 KB Output is correct
7 Correct 14 ms 22108 KB Output is correct
8 Correct 15 ms 22164 KB Output is correct
9 Correct 16 ms 21988 KB Output is correct
10 Correct 15 ms 21976 KB Output is correct
11 Correct 110 ms 66272 KB Output is correct
12 Correct 95 ms 66680 KB Output is correct
13 Correct 116 ms 66468 KB Output is correct
14 Correct 87 ms 66384 KB Output is correct
15 Correct 89 ms 66388 KB Output is correct
16 Correct 98 ms 66244 KB Output is correct
17 Correct 87 ms 66392 KB Output is correct
18 Correct 95 ms 66380 KB Output is correct
19 Correct 87 ms 66384 KB Output is correct
20 Correct 86 ms 66396 KB Output is correct
21 Correct 434 ms 202040 KB Output is correct
22 Correct 419 ms 202008 KB Output is correct
23 Correct 419 ms 201812 KB Output is correct
24 Correct 404 ms 202408 KB Output is correct
25 Correct 476 ms 201968 KB Output is correct
26 Correct 422 ms 201920 KB Output is correct
27 Correct 407 ms 201812 KB Output is correct
28 Correct 401 ms 201812 KB Output is correct
29 Correct 418 ms 201816 KB Output is correct
30 Correct 394 ms 201812 KB Output is correct