oj.uz

Submission #1106182

# Submission time Handle Problem Language Result Execution time Memory
1106182 2024-10-29T13:28:49 Z duytuandao21 Index (COCI21_index) C++17
110 / 110
 839 ms 52328 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[100 * 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 2808 KB Output is correct
6 Correct 4 ms 2640 KB Output is correct
7 Correct 4 ms 2640 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 4 ms 2640 KB Output is correct
10 Correct 7 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 2808 KB Output is correct
6 Correct 4 ms 2640 KB Output is correct
7 Correct 4 ms 2640 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 4 ms 2640 KB Output is correct
10 Correct 7 ms 2640 KB Output is correct
11 Correct 163 ms 13636 KB Output is correct
12 Correct 163 ms 13424 KB Output is correct
13 Correct 158 ms 13552 KB Output is correct
14 Correct 152 ms 13644 KB Output is correct
15 Correct 166 ms 13640 KB Output is correct
16 Correct 154 ms 13640 KB Output is correct
17 Correct 151 ms 13640 KB Output is correct
18 Correct 159 ms 13440 KB Output is correct
19 Correct 163 ms 13644 KB Output is correct
20 Correct 149 ms 13644 KB Output is correct

Subtask #3
50.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 2808 KB Output is correct
6 Correct 4 ms 2640 KB Output is correct
7 Correct 4 ms 2640 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 4 ms 2640 KB Output is correct
10 Correct 7 ms 2640 KB Output is correct
11 Correct 163 ms 13636 KB Output is correct
12 Correct 163 ms 13424 KB Output is correct
13 Correct 158 ms 13552 KB Output is correct
14 Correct 152 ms 13644 KB Output is correct
15 Correct 166 ms 13640 KB Output is correct
16 Correct 154 ms 13640 KB Output is correct
17 Correct 151 ms 13640 KB Output is correct
18 Correct 159 ms 13440 KB Output is correct
19 Correct 163 ms 13644 KB Output is correct
20 Correct 149 ms 13644 KB Output is correct
21 Correct 764 ms 51272 KB Output is correct
22 Correct 721 ms 52148 KB Output is correct
23 Correct 704 ms 52064 KB Output is correct
24 Correct 688 ms 52180 KB Output is correct
25 Correct 692 ms 52068 KB Output is correct
26 Correct 708 ms 52048 KB Output is correct
27 Correct 809 ms 52224 KB Output is correct
28 Correct 761 ms 52212 KB Output is correct
29 Correct 789 ms 52328 KB Output is correct
30 Correct 839 ms 52136 KB Output is correct