oj.uz

Submission #1027392

# Submission time Handle Problem Language Result Execution time Memory
1027392 2024-07-19T05:41:01 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 1670 ms 177684 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
tree_order_statistics_node_update> Tree;

const int N = 100100;
const int M = (1 << 18);

Tree st[2 * M];

void insert(int x, pair<int, int> a) {
    // cout << "added: " << '(' << x << ' ' << a.first << ')' << '\n';
    for (x += M; x; x >>= 1) {
        st[x].insert(a);
    }
}

int get(int x, int y) {
    int ans = 0;
    for (int ql = x + M, qr = 2 * M; ql < qr; ql >>= 1, qr >>= 1) {
        if (ql & 1) {
            ans += (int)st[ql].size() - st[ql].order_of_key({y, 0});
            ql++;
        } 
        if (qr & 1) {
            --qr;
            ans += (int)st[qr].size() - st[qr].order_of_key({y, 0});
        }
    }
    return ans;
}

int n, q;
pair<int, int> p[N];
array<int, 4> t[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> q;
    int res[q];

    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
    }
    for (int i = 0; i < q; i++) {
        cin >> t[i][0] >> t[i][1] >> t[i][2];
        t[i][3] = i;
    }

    vector<int> keys;
    for (int i = 0; i < n; i++) keys.push_back(p[i].first);
    for (int i = 0; i < q; i++) keys.push_back(t[i][0]);
    
    sort(keys.begin(), keys.end());
    keys.erase(unique(keys.begin(), keys.end()), keys.end());

    sort(p, p + n, [](pair<int, int> a, pair<int, int> b) {
        return a.first + a.second > b.first + b.second;
    });
    sort(t, t + q, [](array<int, 4> a, array<int, 4> b) {
        return a[2] > b[2];
    });
    
    int l = 0;
    for (int i = 0; i < q; i++) {
        auto cur = t[i];
        int z = cur[2];
        while (l < n && p[l].first + p[l].second >= z) {
            int x = lower_bound(keys.begin(), keys.end(), p[l].first) - keys.begin();
            insert(x, {p[l].second, l});
            l++;
        }
        int x = cur[0], y = cur[1];
        x = lower_bound(keys.begin(), keys.end(), x) - keys.begin();
        // cout << "ask: " << '(' << x << ' ' << y << ')' << '\n';    
        res[cur[3]] = get(x, y);
    }
    
    for (int i = 0; i < q; i++) {
        cout << res[i] << '\n';
    }

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49752 KB Output is correct
2 Correct 34 ms 49748 KB Output is correct
3 Correct 28 ms 49752 KB Output is correct
4 Correct 28 ms 49756 KB Output is correct
5 Correct 28 ms 49756 KB Output is correct
6 Correct 27 ms 49756 KB Output is correct
7 Correct 42 ms 53572 KB Output is correct
8 Correct 40 ms 53572 KB Output is correct
9 Correct 49 ms 53668 KB Output is correct
10 Correct 42 ms 53548 KB Output is correct
11 Correct 45 ms 53584 KB Output is correct
12 Correct 41 ms 53328 KB Output is correct
13 Correct 41 ms 53584 KB Output is correct
14 Correct 42 ms 53588 KB Output is correct
15 Correct 52 ms 53588 KB Output is correct
16 Correct 42 ms 53416 KB Output is correct
17 Correct 41 ms 53592 KB Output is correct
18 Correct 42 ms 53332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1451 ms 175092 KB Output is correct
2 Correct 1566 ms 175044 KB Output is correct
3 Correct 1670 ms 175120 KB Output is correct
4 Correct 1012 ms 174472 KB Output is correct
5 Correct 872 ms 174416 KB Output is correct
6 Correct 904 ms 173556 KB Output is correct
7 Correct 1523 ms 175124 KB Output is correct
8 Correct 1363 ms 175144 KB Output is correct
9 Correct 1167 ms 175040 KB Output is correct
10 Correct 592 ms 174128 KB Output is correct
11 Correct 795 ms 174120 KB Output is correct
12 Correct 1098 ms 173260 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1451 ms 175092 KB Output is correct
2 Correct 1566 ms 175044 KB Output is correct
3 Correct 1670 ms 175120 KB Output is correct
4 Correct 1012 ms 174472 KB Output is correct
5 Correct 872 ms 174416 KB Output is correct
6 Correct 904 ms 173556 KB Output is correct
7 Correct 1523 ms 175124 KB Output is correct
8 Correct 1363 ms 175144 KB Output is correct
9 Correct 1167 ms 175040 KB Output is correct
10 Correct 592 ms 174128 KB Output is correct
11 Correct 795 ms 174120 KB Output is correct
12 Correct 1098 ms 173260 KB Output is correct
13 Correct 1243 ms 175492 KB Output is correct
14 Correct 1427 ms 175572 KB Output is correct
15 Correct 1341 ms 175312 KB Output is correct
16 Correct 844 ms 174796 KB Output is correct
17 Correct 726 ms 174792 KB Output is correct
18 Correct 675 ms 173584 KB Output is correct
19 Correct 1291 ms 175568 KB Output is correct
20 Correct 1226 ms 175560 KB Output is correct
21 Correct 1157 ms 175628 KB Output is correct
22 Correct 627 ms 174288 KB Output is correct
23 Correct 833 ms 174284 KB Output is correct
24 Correct 1097 ms 173312 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49752 KB Output is correct
2 Correct 34 ms 49748 KB Output is correct
3 Correct 28 ms 49752 KB Output is correct
4 Correct 28 ms 49756 KB Output is correct
5 Correct 28 ms 49756 KB Output is correct
6 Correct 27 ms 49756 KB Output is correct
7 Correct 42 ms 53572 KB Output is correct
8 Correct 40 ms 53572 KB Output is correct
9 Correct 49 ms 53668 KB Output is correct
10 Correct 42 ms 53548 KB Output is correct
11 Correct 45 ms 53584 KB Output is correct
12 Correct 41 ms 53328 KB Output is correct
13 Correct 41 ms 53584 KB Output is correct
14 Correct 42 ms 53588 KB Output is correct
15 Correct 52 ms 53588 KB Output is correct
16 Correct 42 ms 53416 KB Output is correct
17 Correct 41 ms 53592 KB Output is correct
18 Correct 42 ms 53332 KB Output is correct
19 Correct 1451 ms 175092 KB Output is correct
20 Correct 1566 ms 175044 KB Output is correct
21 Correct 1670 ms 175120 KB Output is correct
22 Correct 1012 ms 174472 KB Output is correct
23 Correct 872 ms 174416 KB Output is correct
24 Correct 904 ms 173556 KB Output is correct
25 Correct 1523 ms 175124 KB Output is correct
26 Correct 1363 ms 175144 KB Output is correct
27 Correct 1167 ms 175040 KB Output is correct
28 Correct 592 ms 174128 KB Output is correct
29 Correct 795 ms 174120 KB Output is correct
30 Correct 1098 ms 173260 KB Output is correct
31 Correct 1243 ms 175492 KB Output is correct
32 Correct 1427 ms 175572 KB Output is correct
33 Correct 1341 ms 175312 KB Output is correct
34 Correct 844 ms 174796 KB Output is correct
35 Correct 726 ms 174792 KB Output is correct
36 Correct 675 ms 173584 KB Output is correct
37 Correct 1291 ms 175568 KB Output is correct
38 Correct 1226 ms 175560 KB Output is correct
39 Correct 1157 ms 175628 KB Output is correct
40 Correct 627 ms 174288 KB Output is correct
41 Correct 833 ms 174284 KB Output is correct
42 Correct 1097 ms 173312 KB Output is correct
43 Correct 1315 ms 177608 KB Output is correct
44 Correct 1206 ms 177580 KB Output is correct
45 Correct 1486 ms 177536 KB Output is correct
46 Correct 867 ms 176080 KB Output is correct
47 Correct 1077 ms 176000 KB Output is correct
48 Correct 689 ms 173776 KB Output is correct
49 Correct 1324 ms 177684 KB Output is correct
50 Correct 1249 ms 177368 KB Output is correct
51 Correct 1170 ms 177248 KB Output is correct
52 Correct 1094 ms 176072 KB Output is correct
53 Correct 767 ms 175048 KB Output is correct