oj.uz

Submission #839431

# Submission time Handle Problem Language Result Execution time Memory
839431 2023-08-30T03:01:53 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 2024 ms 164292 KB 
#include <iostream>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
namespace __gnu_pbds{
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
struct QUERY {
    int x, y, z, num;
} b[100005];
struct GRADE {
    int x, y;
} a[100005];
int res[100005];
bool cmp(QUERY aa, QUERY bb) {
    return aa.x > bb.x;
}
bool cmp2(GRADE aa, GRADE bb) {
    return aa.x > bb.x;
}
ordered_set t[800005];
map<int, int> mm;
void update(int v, int tl, int tr, int x, int y) {
    if (tl == tr) {
        t[v].insert(y);
        return;
    }
    int mid = (tl + tr) / 2;
    if (mid >= x) update(v * 2, tl, mid, x, y);
    else update(v * 2 + 1, mid + 1, tr, x, y);
    t[v].insert(y);
}
int sum(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return t[v].size() - t[v].order_of_key(x);
    }
    int mid = (tl + tr) / 2;
    return sum(v * 2, tl, mid, l, min(r, mid), x) + sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, z = 0;
    cin >> n >> q;
    vector<int> v;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
        v.push_back(a[i].y);
    }
    sort(a + 1, a + n + 1, cmp2);
    for (int i = 0; i < q; i++) {
        cin >> b[i].x >> b[i].y >> b[i].z;
        v.push_back(b[i].y);
        b[i].num = i;
    }
    sort(v.begin(), v.end());
    for (int w : v) {
        if (!mm.count(w)) {
            mm[w] = ++z;
        }
    }
    sort(b, b + q, cmp);
    int j = 1;
    for (int i = 0; i < q; i++) {
        while (a[j].x >= b[i].x && j <= n) {
            update(1, 1, z, mm[a[j].y], a[j].x + a[j].y);
            j++;
            //cout << j << " " << a[j].x << " " << b[i].x << endl;
        }
        res[b[i].num] = sum(1, 1, z, mm[b[i].y], z, b[i].z);
    }
    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 44 ms 62924 KB Output is correct
2 Correct 44 ms 62928 KB Output is correct
3 Correct 44 ms 62908 KB Output is correct
4 Correct 43 ms 62912 KB Output is correct
5 Correct 45 ms 62844 KB Output is correct
6 Correct 46 ms 62936 KB Output is correct
7 Correct 61 ms 65256 KB Output is correct
8 Correct 64 ms 65352 KB Output is correct
9 Correct 56 ms 65228 KB Output is correct
10 Correct 48 ms 63620 KB Output is correct
11 Correct 57 ms 65268 KB Output is correct
12 Correct 48 ms 63652 KB Output is correct
13 Correct 55 ms 65272 KB Output is correct
14 Correct 59 ms 65228 KB Output is correct
15 Correct 57 ms 65188 KB Output is correct
16 Correct 54 ms 65244 KB Output is correct
17 Correct 46 ms 63236 KB Output is correct
18 Correct 46 ms 63444 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 153096 KB Output is correct
2 Correct 1564 ms 153124 KB Output is correct
3 Correct 1692 ms 153192 KB Output is correct
4 Correct 274 ms 88332 KB Output is correct
5 Correct 1154 ms 153116 KB Output is correct
6 Correct 239 ms 88300 KB Output is correct
7 Correct 1753 ms 153244 KB Output is correct
8 Correct 1538 ms 150148 KB Output is correct
9 Correct 1407 ms 150136 KB Output is correct
10 Correct 1083 ms 152976 KB Output is correct
11 Correct 141 ms 76180 KB Output is correct
12 Correct 251 ms 80740 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 153096 KB Output is correct
2 Correct 1564 ms 153124 KB Output is correct
3 Correct 1692 ms 153192 KB Output is correct
4 Correct 274 ms 88332 KB Output is correct
5 Correct 1154 ms 153116 KB Output is correct
6 Correct 239 ms 88300 KB Output is correct
7 Correct 1753 ms 153244 KB Output is correct
8 Correct 1538 ms 150148 KB Output is correct
9 Correct 1407 ms 150136 KB Output is correct
10 Correct 1083 ms 152976 KB Output is correct
11 Correct 141 ms 76180 KB Output is correct
12 Correct 251 ms 80740 KB Output is correct
13 Correct 1789 ms 153080 KB Output is correct
14 Correct 1727 ms 153108 KB Output is correct
15 Correct 1640 ms 153212 KB Output is correct
16 Correct 304 ms 88264 KB Output is correct
17 Correct 1237 ms 153164 KB Output is correct
18 Correct 259 ms 88376 KB Output is correct
19 Correct 1756 ms 153168 KB Output is correct
20 Correct 1879 ms 153200 KB Output is correct
21 Correct 2021 ms 152244 KB Output is correct
22 Correct 1097 ms 153052 KB Output is correct
23 Correct 150 ms 76144 KB Output is correct
24 Correct 253 ms 80660 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 62924 KB Output is correct
2 Correct 44 ms 62928 KB Output is correct
3 Correct 44 ms 62908 KB Output is correct
4 Correct 43 ms 62912 KB Output is correct
5 Correct 45 ms 62844 KB Output is correct
6 Correct 46 ms 62936 KB Output is correct
7 Correct 61 ms 65256 KB Output is correct
8 Correct 64 ms 65352 KB Output is correct
9 Correct 56 ms 65228 KB Output is correct
10 Correct 48 ms 63620 KB Output is correct
11 Correct 57 ms 65268 KB Output is correct
12 Correct 48 ms 63652 KB Output is correct
13 Correct 55 ms 65272 KB Output is correct
14 Correct 59 ms 65228 KB Output is correct
15 Correct 57 ms 65188 KB Output is correct
16 Correct 54 ms 65244 KB Output is correct
17 Correct 46 ms 63236 KB Output is correct
18 Correct 46 ms 63444 KB Output is correct
19 Correct 1614 ms 153096 KB Output is correct
20 Correct 1564 ms 153124 KB Output is correct
21 Correct 1692 ms 153192 KB Output is correct
22 Correct 274 ms 88332 KB Output is correct
23 Correct 1154 ms 153116 KB Output is correct
24 Correct 239 ms 88300 KB Output is correct
25 Correct 1753 ms 153244 KB Output is correct
26 Correct 1538 ms 150148 KB Output is correct
27 Correct 1407 ms 150136 KB Output is correct
28 Correct 1083 ms 152976 KB Output is correct
29 Correct 141 ms 76180 KB Output is correct
30 Correct 251 ms 80740 KB Output is correct
31 Correct 1789 ms 153080 KB Output is correct
32 Correct 1727 ms 153108 KB Output is correct
33 Correct 1640 ms 153212 KB Output is correct
34 Correct 304 ms 88264 KB Output is correct
35 Correct 1237 ms 153164 KB Output is correct
36 Correct 259 ms 88376 KB Output is correct
37 Correct 1756 ms 153168 KB Output is correct
38 Correct 1879 ms 153200 KB Output is correct
39 Correct 2021 ms 152244 KB Output is correct
40 Correct 1097 ms 153052 KB Output is correct
41 Correct 150 ms 76144 KB Output is correct
42 Correct 253 ms 80660 KB Output is correct
43 Correct 1884 ms 164288 KB Output is correct
44 Correct 2024 ms 164132 KB Output is correct
45 Correct 1857 ms 164152 KB Output is correct
46 Correct 339 ms 88284 KB Output is correct
47 Correct 1370 ms 164212 KB Output is correct
48 Correct 263 ms 88136 KB Output is correct
49 Correct 1991 ms 164292 KB Output is correct
50 Correct 1910 ms 164164 KB Output is correct
51 Correct 2017 ms 164196 KB Output is correct
52 Correct 1377 ms 164020 KB Output is correct
53 Correct 205 ms 76208 KB Output is correct