oj.uz

Submission #954104

# Submission time Handle Problem Language Result Execution time Memory
954104 2024-03-27T09:34:53 Z Beerus13 Index (COCI21_index) C++14
110 / 110
 1089 ms 53984 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
const int K = 20;
const int inf = 1e9;

struct node {
    int x, l, r;
    node() { x = l = r = 0; }
    node(int x, int l, int r) : x(x), l(l), r(r) {}
};

int n, q, a[N], nNode, nver, ver[N];
node st[N * K];

void refine(int cur) {
    st[cur].x = st[st[cur].l].x + st[st[cur].r].x;
}

int update(int pos, int val, int old, int l = 1, int r = N - 1) {
    int cur = ++nNode;
    if(l == r) {
        st[cur] = node(st[old].x + val, 0, 0);
        return cur;
    }
    int m = l + r >> 1;
    if(pos <= m) {
        st[cur].l = update(pos, val, st[old].l, l, m);
        st[cur].r = st[old].r;
    }
    else {
        st[cur].l = st[old].l;
        st[cur].r = update(pos, val, st[old].r, m + 1, r);
    }
    refine(cur);
    return cur;
}

int get(int ver, int u, int v, int l = 1, int r = N - 1) {
    if(u > r || v < l) return 0;
    if(u <= l && r <= v) return st[ver].x;
    int m = l + r >> 1;
    return get(st[ver].l, u, v, l, m) + get(st[ver].r, u, v, m + 1, r);
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        ver[i] = update(a[i], 1, ver[i - 1]);
    }
    while(q--) {
        int ql, qr; cin >> ql >> qr;
        int l = 1, r = 2e5, ans;
        while(l <= r) {
            int m = l + r >> 1;
            if(get(ver[qr], m, N - 1) - get(ver[ql - 1], m, N - 1) >= m) ans = m, l = m + 1;
            else r = m - 1;
        }
        cout << ans << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message

index.cpp: In function 'int update(int, int, int, int, int)':
index.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int m = l + r >> 1;
      |             ~~^~~
index.cpp: In function 'int get(int, int, int, int, int)':
index.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int m = l + r >> 1;
      |             ~~^~~
index.cpp: In function 'void solve()':
index.cpp:57:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |             int m = l + r >> 1;
      |                     ~~^~~
index.cpp:61:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |         cout << ans << '\n';
      |                        ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 47708 KB Output is correct
2 Correct 12 ms 47708 KB Output is correct
3 Correct 13 ms 47708 KB Output is correct
4 Correct 13 ms 47708 KB Output is correct
5 Correct 13 ms 47848 KB Output is correct
6 Correct 13 ms 47760 KB Output is correct
7 Correct 13 ms 47852 KB Output is correct
8 Correct 12 ms 47704 KB Output is correct
9 Correct 12 ms 47712 KB Output is correct
10 Correct 13 ms 47848 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 47708 KB Output is correct
2 Correct 12 ms 47708 KB Output is correct
3 Correct 13 ms 47708 KB Output is correct
4 Correct 13 ms 47708 KB Output is correct
5 Correct 13 ms 47848 KB Output is correct
6 Correct 13 ms 47760 KB Output is correct
7 Correct 13 ms 47852 KB Output is correct
8 Correct 12 ms 47704 KB Output is correct
9 Correct 12 ms 47712 KB Output is correct
10 Correct 13 ms 47848 KB Output is correct
11 Correct 217 ms 48956 KB Output is correct
12 Correct 208 ms 48980 KB Output is correct
13 Correct 210 ms 49052 KB Output is correct
14 Correct 215 ms 49100 KB Output is correct
15 Correct 207 ms 48976 KB Output is correct
16 Correct 211 ms 49136 KB Output is correct
17 Correct 216 ms 49268 KB Output is correct
18 Correct 199 ms 49112 KB Output is correct
19 Correct 224 ms 49044 KB Output is correct
20 Correct 233 ms 49020 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 47708 KB Output is correct
2 Correct 12 ms 47708 KB Output is correct
3 Correct 13 ms 47708 KB Output is correct
4 Correct 13 ms 47708 KB Output is correct
5 Correct 13 ms 47848 KB Output is correct
6 Correct 13 ms 47760 KB Output is correct
7 Correct 13 ms 47852 KB Output is correct
8 Correct 12 ms 47704 KB Output is correct
9 Correct 12 ms 47712 KB Output is correct
10 Correct 13 ms 47848 KB Output is correct
11 Correct 217 ms 48956 KB Output is correct
12 Correct 208 ms 48980 KB Output is correct
13 Correct 210 ms 49052 KB Output is correct
14 Correct 215 ms 49100 KB Output is correct
15 Correct 207 ms 48976 KB Output is correct
16 Correct 211 ms 49136 KB Output is correct
17 Correct 216 ms 49268 KB Output is correct
18 Correct 199 ms 49112 KB Output is correct
19 Correct 224 ms 49044 KB Output is correct
20 Correct 233 ms 49020 KB Output is correct
21 Correct 1089 ms 53724 KB Output is correct
22 Correct 954 ms 53772 KB Output is correct
23 Correct 1008 ms 53696 KB Output is correct
24 Correct 1026 ms 53804 KB Output is correct
25 Correct 971 ms 53984 KB Output is correct
26 Correct 986 ms 53828 KB Output is correct
27 Correct 979 ms 53844 KB Output is correct
28 Correct 960 ms 53920 KB Output is correct
29 Correct 1004 ms 53860 KB Output is correct
30 Correct 963 ms 53732 KB Output is correct