oj.uz

Submission #1106179

# Submission time Handle Problem Language Result Execution time Memory
1106179 2024-10-29T13:26:23 Z duytuandao21 Index (COCI21_index) C++17
20 / 110
 2226 ms 29112 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[4 * 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, x, 1);
    }
    while (q--) {
        int l, r; cin >> l >> r;
        int lo = 1, hi = N;
        int ans;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (get(ver[r], 1, N, mid, N) - get(ver[l - 1], 1, N, mid, N) >= mid) {
                ans = mid;
                lo = mid + 1;
            } else hi = mid - 1; 
        }
        cout << ans << '\n';
    }
}

Compilation message

index.cpp: In function 'int main()':
index.cpp:72:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |         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 2744 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 2736 KB Output is correct
6 Correct 4 ms 2736 KB Output is correct
7 Correct 4 ms 2640 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 5 ms 2640 KB Output is correct
10 Correct 4 ms 2640 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2640 KB Output is correct
2 Correct 4 ms 2744 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 2736 KB Output is correct
6 Correct 4 ms 2736 KB Output is correct
7 Correct 4 ms 2640 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 5 ms 2640 KB Output is correct
10 Correct 4 ms 2640 KB Output is correct
11 Runtime error 2226 ms 29112 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2640 KB Output is correct
2 Correct 4 ms 2744 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 2736 KB Output is correct
6 Correct 4 ms 2736 KB Output is correct
7 Correct 4 ms 2640 KB Output is correct
8 Correct 4 ms 2640 KB Output is correct
9 Correct 5 ms 2640 KB Output is correct
10 Correct 4 ms 2640 KB Output is correct
11 Runtime error 2226 ms 29112 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -