10707 2024. 04. 10 09:43:34 szil Telefonközpont cpp17 Elfogadva 100/100 128ms 7432 KiB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 300'001;

int pref[MAXN], a[MAXN], tree[2*MAXN], n, m, q;

void upd(int u, int k) {
    tree[u += m] = k;
    for (u /= 2; u >= 1; u /= 2) {
        tree[u] = max(tree[2*u], tree[2*u+1]);
    }
}

int qry(int l, int r) {
    int res = 0; l += m; r += m;
    while (l <= r) {
        if (l % 2 == 1) res = max(res, tree[l++]);
        if (r % 2 == 0) res = max(res, tree[r--]);
        l /= 2; r /= 2;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> m >> n >> q;
    for (int i = 1; i <= n; i++) {
        int l, r; cin >> l >> r;
        pref[l]++;
        pref[r+1]--;
    }
    for (int i = 1; i <= m; i++) {
        pref[i] += pref[i-1];
        upd(i, pref[i]);
    }
    while (q--) {
        int l, r; cin >> l >> r;
        cout << qry(l, r) << "\n";
    }
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1900 KiB
2 Elfogadva 3ms 2108 KiB
subtask2 20/20
3 Elfogadva 3ms 2304 KiB
4 Elfogadva 3ms 2648 KiB
5 Elfogadva 3ms 2604 KiB
6 Elfogadva 3ms 2688 KiB
7 Elfogadva 3ms 2860 KiB
8 Elfogadva 3ms 2940 KiB
9 Elfogadva 3ms 3024 KiB
subtask3 20/20
10 Elfogadva 3ms 2304 KiB
11 Elfogadva 3ms 2648 KiB
12 Elfogadva 3ms 2604 KiB
13 Elfogadva 3ms 2688 KiB
14 Elfogadva 3ms 2860 KiB
15 Elfogadva 3ms 2940 KiB
16 Elfogadva 3ms 3024 KiB
17 Elfogadva 4ms 3332 KiB
18 Elfogadva 4ms 3284 KiB
19 Elfogadva 4ms 3316 KiB
20 Elfogadva 4ms 3280 KiB
21 Elfogadva 4ms 3280 KiB
22 Elfogadva 4ms 3284 KiB
23 Elfogadva 4ms 3292 KiB
subtask4 60/60
24 Elfogadva 3ms 2304 KiB
25 Elfogadva 3ms 2648 KiB
26 Elfogadva 3ms 2604 KiB
27 Elfogadva 3ms 2688 KiB
28 Elfogadva 3ms 2860 KiB
29 Elfogadva 3ms 2940 KiB
30 Elfogadva 3ms 3024 KiB
31 Elfogadva 4ms 3332 KiB
32 Elfogadva 4ms 3284 KiB
33 Elfogadva 4ms 3316 KiB
34 Elfogadva 4ms 3280 KiB
35 Elfogadva 4ms 3280 KiB
36 Elfogadva 4ms 3284 KiB
37 Elfogadva 4ms 3292 KiB
38 Elfogadva 128ms 6884 KiB
39 Elfogadva 127ms 6900 KiB
40 Elfogadva 125ms 7100 KiB
41 Elfogadva 123ms 7212 KiB
42 Elfogadva 123ms 7432 KiB
43 Elfogadva 123ms 7424 KiB
44 Elfogadva 123ms 7432 KiB