oj.uz

Submission #1106181

# Submission time Handle Problem Language Result Execution time Memory
1106181 2024-10-29T13:28:15 Z duytuandao21 Index (COCI21_index) C++17
60 / 110
 166 ms 52248 KB 
/* chumeodiia */
/* TRY HARD */
#include<bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(mask, i) (mask & (1LL << (i)))
// #define int long long
#define mp(x, y) make_pair(x, y)
using namespace std;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int S = 317;
const long long infll = 1e18 + 7;
typedef pair<int, int> pii;

int n, q, nNode;
int a[N], ver[N];
struct Node {
    int left;
    int right;
    int sum;
} seg[10 * N];

int update(int oldId, int l, int r, int p, int v) {
    if (l == r) {
        a[l] += v;
        ++nNode;
        seg[nNode].sum = a[l];
        seg[nNode].left = seg[nNode].right = 0;
        return nNode;
    }
    int mid = (l + r) / 2;
    int cur = ++nNode;
    if (p <= mid) {
        seg[cur].left = update(seg[oldId].left, l, mid, p, v);
        seg[cur].right = seg[oldId].right;
        seg[cur].sum = seg[seg[cur].left].sum + seg[seg[cur].right].sum;
    }
    else {  
        seg[cur].left = seg[oldId].left;
        seg[cur].right = update(seg[oldId].right, mid + 1, r, p, v);
        seg[cur].sum = seg[seg[cur].left].sum + seg[seg[cur].right].sum;
    }
    return cur;
}
int get(int id, int l, int r, int u, int v) {
    if (r < u || l > v) return 0;
    if (l >= u && r <= v) return seg[id].sum;
    int mid = (l + r) / 2;
    return get(seg[id].left, l, mid, u, v) + get(seg[id].right, mid + 1, r, u, v);
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        ver[i] = update(ver[i - 1], 1, N - 1, x, 1);
    }
    while (q--) {
        int l, r; cin >> l >> r;
        int lo = 1, hi = N - 1;
        int ans = 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (get(ver[r], 1, N - 1, mid, N - 1) - get(ver[l - 1], 1, N - 1, mid, N - 1) >= mid) {
                ans = mid;
                lo = mid + 1;
            } else hi = mid - 1; 
        }
        cout << ans << '\n';
    }
}

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2640 KB Output is correct
2 Correct 4 ms 2640 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 4 ms 2640 KB Output is correct
5 Correct 4 ms 2640 KB Output is correct
6 Correct 4 ms 2640 KB Output is correct
7 Correct 4 ms 2720 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 4 ms 2640 KB Output is correct
10 Correct 6 ms 2640 KB Output is correct
11 Correct 157 ms 13640 KB Output is correct
12 Correct 166 ms 14404 KB Output is correct
13 Correct 158 ms 14408 KB Output is correct
14 Correct 152 ms 14380 KB Output is correct
15 Correct 154 ms 14408 KB Output is correct
16 Correct 154 ms 14384 KB Output is correct
17 Correct 152 ms 14388 KB Output is correct
18 Correct 150 ms 14408 KB Output is correct
19 Correct 150 ms 14408 KB Output is correct
20 Correct 156 ms 14408 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2640 KB Output is correct
2 Correct 4 ms 2640 KB Output is correct
3 Correct 4 ms 2640 KB Output is correct
4 Correct 4 ms 2640 KB Output is correct
5 Correct 4 ms 2640 KB Output is correct
6 Correct 4 ms 2640 KB Output is correct
7 Correct 4 ms 2720 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 4 ms 2640 KB Output is correct
10 Correct 6 ms 2640 KB Output is correct
11 Correct 157 ms 13640 KB Output is correct
12 Correct 166 ms 14404 KB Output is correct
13 Correct 158 ms 14408 KB Output is correct
14 Correct 152 ms 14380 KB Output is correct
15 Correct 154 ms 14408 KB Output is correct
16 Correct 154 ms 14384 KB Output is correct
17 Correct 152 ms 14388 KB Output is correct
18 Correct 150 ms 14408 KB Output is correct
19 Correct 150 ms 14408 KB Output is correct
20 Correct 156 ms 14408 KB Output is correct
21 Runtime error 69 ms 52248 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -