oj.uz

Submission #839429

# Submission time Handle Problem Language Result Execution time Memory
839429 2023-08-30T03:00:35 Z adaawf Examination (JOI19_examination) C++14
100 / 100
 2144 ms 164252 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 41 ms 62932 KB Output is correct
2 Correct 41 ms 62940 KB Output is correct
3 Correct 37 ms 62828 KB Output is correct
4 Correct 38 ms 62932 KB Output is correct
5 Correct 38 ms 62932 KB Output is correct
6 Correct 44 ms 62880 KB Output is correct
7 Correct 54 ms 65228 KB Output is correct
8 Correct 54 ms 65228 KB Output is correct
9 Correct 51 ms 65224 KB Output is correct
10 Correct 43 ms 63700 KB Output is correct
11 Correct 60 ms 65224 KB Output is correct
12 Correct 55 ms 63604 KB Output is correct
13 Correct 51 ms 65264 KB Output is correct
14 Correct 52 ms 65256 KB Output is correct
15 Correct 55 ms 65268 KB Output is correct
16 Correct 55 ms 65148 KB Output is correct
17 Correct 52 ms 63348 KB Output is correct
18 Correct 52 ms 63564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1821 ms 153156 KB Output is correct
2 Correct 1649 ms 153156 KB Output is correct
3 Correct 1737 ms 153132 KB Output is correct
4 Correct 257 ms 88268 KB Output is correct
5 Correct 1240 ms 153148 KB Output is correct
6 Correct 284 ms 88292 KB Output is correct
7 Correct 1757 ms 153228 KB Output is correct
8 Correct 1852 ms 150108 KB Output is correct
9 Correct 1714 ms 150120 KB Output is correct
10 Correct 1171 ms 153008 KB Output is correct
11 Correct 145 ms 76136 KB Output is correct
12 Correct 251 ms 80728 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1821 ms 153156 KB Output is correct
2 Correct 1649 ms 153156 KB Output is correct
3 Correct 1737 ms 153132 KB Output is correct
4 Correct 257 ms 88268 KB Output is correct
5 Correct 1240 ms 153148 KB Output is correct
6 Correct 284 ms 88292 KB Output is correct
7 Correct 1757 ms 153228 KB Output is correct
8 Correct 1852 ms 150108 KB Output is correct
9 Correct 1714 ms 150120 KB Output is correct
10 Correct 1171 ms 153008 KB Output is correct
11 Correct 145 ms 76136 KB Output is correct
12 Correct 251 ms 80728 KB Output is correct
13 Correct 2028 ms 153088 KB Output is correct
14 Correct 2144 ms 153184 KB Output is correct
15 Correct 1723 ms 153128 KB Output is correct
16 Correct 291 ms 88356 KB Output is correct
17 Correct 1337 ms 153116 KB Output is correct
18 Correct 284 ms 88396 KB Output is correct
19 Correct 2101 ms 153124 KB Output is correct
20 Correct 1832 ms 153164 KB Output is correct
21 Correct 1993 ms 152112 KB Output is correct
22 Correct 1087 ms 152960 KB Output is correct
23 Correct 143 ms 76184 KB Output is correct
24 Correct 248 ms 80780 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 62932 KB Output is correct
2 Correct 41 ms 62940 KB Output is correct
3 Correct 37 ms 62828 KB Output is correct
4 Correct 38 ms 62932 KB Output is correct
5 Correct 38 ms 62932 KB Output is correct
6 Correct 44 ms 62880 KB Output is correct
7 Correct 54 ms 65228 KB Output is correct
8 Correct 54 ms 65228 KB Output is correct
9 Correct 51 ms 65224 KB Output is correct
10 Correct 43 ms 63700 KB Output is correct
11 Correct 60 ms 65224 KB Output is correct
12 Correct 55 ms 63604 KB Output is correct
13 Correct 51 ms 65264 KB Output is correct
14 Correct 52 ms 65256 KB Output is correct
15 Correct 55 ms 65268 KB Output is correct
16 Correct 55 ms 65148 KB Output is correct
17 Correct 52 ms 63348 KB Output is correct
18 Correct 52 ms 63564 KB Output is correct
19 Correct 1821 ms 153156 KB Output is correct
20 Correct 1649 ms 153156 KB Output is correct
21 Correct 1737 ms 153132 KB Output is correct
22 Correct 257 ms 88268 KB Output is correct
23 Correct 1240 ms 153148 KB Output is correct
24 Correct 284 ms 88292 KB Output is correct
25 Correct 1757 ms 153228 KB Output is correct
26 Correct 1852 ms 150108 KB Output is correct
27 Correct 1714 ms 150120 KB Output is correct
28 Correct 1171 ms 153008 KB Output is correct
29 Correct 145 ms 76136 KB Output is correct
30 Correct 251 ms 80728 KB Output is correct
31 Correct 2028 ms 153088 KB Output is correct
32 Correct 2144 ms 153184 KB Output is correct
33 Correct 1723 ms 153128 KB Output is correct
34 Correct 291 ms 88356 KB Output is correct
35 Correct 1337 ms 153116 KB Output is correct
36 Correct 284 ms 88396 KB Output is correct
37 Correct 2101 ms 153124 KB Output is correct
38 Correct 1832 ms 153164 KB Output is correct
39 Correct 1993 ms 152112 KB Output is correct
40 Correct 1087 ms 152960 KB Output is correct
41 Correct 143 ms 76184 KB Output is correct
42 Correct 248 ms 80780 KB Output is correct
43 Correct 1969 ms 164116 KB Output is correct
44 Correct 1906 ms 164140 KB Output is correct
45 Correct 1890 ms 164152 KB Output is correct
46 Correct 343 ms 88348 KB Output is correct
47 Correct 1460 ms 164232 KB Output is correct
48 Correct 332 ms 88188 KB Output is correct
49 Correct 2077 ms 164152 KB Output is correct
50 Correct 1923 ms 164252 KB Output is correct
51 Correct 1957 ms 164192 KB Output is correct
52 Correct 1320 ms 163912 KB Output is correct
53 Correct 200 ms 76340 KB Output is correct