Submission #1106182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106182		duytuandao21	Index (COCI21_index)	C++17	110 / 110	839 ms	52328 KiB

index

/* 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 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50