oj.uz

Submission #330893

# Submission time Handle Problem Language Result Execution time Memory
330893 2020-11-26T20:18:23 Z 12tqian Examination (JOI19_examination) C++17
100 / 100
 1951 ms 290564 KB 
#include<bits/stdc++.h>
using namespace std;
const int SZ = (1 << 18);
static char buf[450 << 20];
void* operator new(size_t s) {
    static size_t i = sizeof buf;
    assert(s < i);
    return (void*) & buf[i -= s];
}
void operator delete(void*) {}
// [0, SZ - 1) queries for each axis
template<class T> struct Node {
    T val = 0; 
    Node<T>* c[2];
    Node() { c[0] = c[1] = NULL; }
    void upd(int ind, T v, int L = 0, int R = SZ - 1) { // add v
        if (L == ind && R == ind) { val += v; return; }
        int M = (L + R) / 2;
        if (ind <= M) {
            if (!c[0]) c[0] = new Node();
            c[0]->upd(ind, v, L, M);
        } else {
            if (!c[1]) c[1] = new Node();
            c[1]->upd(ind, v, M + 1, R);
        }
        val = 0; 
        for (int i = 0; i < 2; i++)
            if (c[i]) val += c[i]->val;
    }
    T query(int lo, int hi, int L = 0, int R = SZ - 1) { // query sum of segment
        if (hi < L || R < lo) return 0;
        if (lo <= L && R <= hi) return val;
        int M = (L + R) / 2; 
        T res = 0;
        if (c[0]) res += c[0]->query(lo, hi, L, M);
        if (c[1]) res += c[1]->query(lo, hi, M + 1, R);
        return res;
    }
    void update_2d(int ind, Node* c0, Node* c1, int L = 0, int R = SZ - 1) { // for 2D segtree
        if (L != R) {
            int M = (L + R) / 2;
            if (ind <= M) {
                if (!c[0]) c[0] = new Node();
                c[0]->update_2d(ind, (c0 ? c0->c[0] : NULL), (c1 ? c1->c[0] : NULL), L, M);
            } else {
                if (!c[1]) c[1] = new Node();
                c[1]->update_2d(ind, (c0 ? c0->c[1] : NULL), (c1 ? c1->c[1] : NULL), M + 1, R);
            }
        } 
        val = (c0 ? c0->val : 0) + (c1 ? c1->val : 0);
    }
};
template<class T> struct BITSeg { // 0-indexed implicitly
    std::vector<Node<T>> seg;
    BITSeg() { 
        seg.resize(SZ + 1);
        for (int i = 0; i < SZ; i++)
            seg[i] = Node<T>();
    }
    void upd(int x, int y, int v) { // add v
        x++;
        for (; x < SZ + 1; x += x & -x) 
            seg[x].upd(y, v); 
    }
    T query(int x, int y1, int y2) {
        if (x <= 0) return 0;
        T res = 0; 
        for (; x; x -= x & -x) 
            res += seg[x].query(y1, y2);
        return res; 
    }
    T query(int x1, int x2, int y1, int y2) { // query sum of rectangle
        x1++, x2++;
        return query(x2, y1, y2) - query(x1 - 1, y1, y2); 
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    vector<array<int, 2>> v(n);
    set<int> xs, ys;
    for (int i = 0; i < n; i++) {
        cin >> v[i][0] >> v[i][1];
        xs.insert(v[i][0]);
        ys.insert(v[i][1]);
    }
    vector<int> ans(q);
    vector<array<int, 4>> queries(q);
    for (int i = 0; i < q; i++) {
        queries[i][0] = i;
        cin >> queries[i][1] >> queries[i][2] >> queries[i][3];
        xs.insert(queries[i][1]);
        ys.insert(queries[i][2]);
    }
    map<int, int> mx, my;
    int cnt = 0;
    for (int x : xs) 
        mx[x] = cnt, cnt++;
    cnt = 0;
    for (int y : ys)
        my[y] = cnt, cnt++;
    sort(queries.begin(), queries.end(), [](array<int, 4> a, array<int, 4> b) {
        return a[3] < b[3];
    });
    sort(v.begin(), v.end(), [](array<int, 2> a, array<int, 2> b) {
        return a[0] + a[1] < b[0] + b[1];
    });
    BITSeg<int> seg;
    int qv = n;
    for (int i = q - 1; i >= 0; i--) {
        int sum = queries[i][3];
        while (qv > 0 && v[qv - 1][0] + v[qv - 1][1] >= sum) {
            qv--;
            seg.upd(mx[v[qv][0]], my[v[qv][1]], 1);
        }
        ans[queries[i][0]] = seg.query(mx[queries[i][1]], SZ - 1, my[queries[i][2]], SZ - 1);
    }
    for (int i = 0; i < q; i++) 
        cout << ans[i] << '\n';
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6508 KB Output is correct
2 Correct 5 ms 6508 KB Output is correct
3 Correct 5 ms 6508 KB Output is correct
4 Correct 5 ms 6508 KB Output is correct
5 Correct 5 ms 6508 KB Output is correct
6 Correct 5 ms 6508 KB Output is correct
7 Correct 27 ms 13164 KB Output is correct
8 Correct 26 ms 13164 KB Output is correct
9 Correct 26 ms 13164 KB Output is correct
10 Correct 18 ms 9068 KB Output is correct
11 Correct 23 ms 10604 KB Output is correct
12 Correct 13 ms 6636 KB Output is correct
13 Correct 29 ms 13164 KB Output is correct
14 Correct 28 ms 13164 KB Output is correct
15 Correct 28 ms 13164 KB Output is correct
16 Correct 22 ms 10732 KB Output is correct
17 Correct 15 ms 8812 KB Output is correct
18 Correct 11 ms 6636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1891 ms 220780 KB Output is correct
2 Correct 1876 ms 220780 KB Output is correct
3 Correct 1832 ms 220868 KB Output is correct
4 Correct 623 ms 55712 KB Output is correct
5 Correct 601 ms 85484 KB Output is correct
6 Correct 263 ms 9840 KB Output is correct
7 Correct 1444 ms 211228 KB Output is correct
8 Correct 1640 ms 211168 KB Output is correct
9 Correct 1271 ms 202524 KB Output is correct
10 Correct 533 ms 81836 KB Output is correct
11 Correct 443 ms 47428 KB Output is correct
12 Correct 220 ms 9580 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1891 ms 220780 KB Output is correct
2 Correct 1876 ms 220780 KB Output is correct
3 Correct 1832 ms 220868 KB Output is correct
4 Correct 623 ms 55712 KB Output is correct
5 Correct 601 ms 85484 KB Output is correct
6 Correct 263 ms 9840 KB Output is correct
7 Correct 1444 ms 211228 KB Output is correct
8 Correct 1640 ms 211168 KB Output is correct
9 Correct 1271 ms 202524 KB Output is correct
10 Correct 533 ms 81836 KB Output is correct
11 Correct 443 ms 47428 KB Output is correct
12 Correct 220 ms 9580 KB Output is correct
13 Correct 1614 ms 220664 KB Output is correct
14 Correct 1776 ms 221004 KB Output is correct
15 Correct 1793 ms 220808 KB Output is correct
16 Correct 524 ms 55788 KB Output is correct
17 Correct 544 ms 85612 KB Output is correct
18 Correct 253 ms 9836 KB Output is correct
19 Correct 1584 ms 220696 KB Output is correct
20 Correct 1700 ms 220932 KB Output is correct
21 Correct 1376 ms 214372 KB Output is correct
22 Correct 505 ms 82028 KB Output is correct
23 Correct 420 ms 47340 KB Output is correct
24 Correct 221 ms 9452 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6508 KB Output is correct
2 Correct 5 ms 6508 KB Output is correct
3 Correct 5 ms 6508 KB Output is correct
4 Correct 5 ms 6508 KB Output is correct
5 Correct 5 ms 6508 KB Output is correct
6 Correct 5 ms 6508 KB Output is correct
7 Correct 27 ms 13164 KB Output is correct
8 Correct 26 ms 13164 KB Output is correct
9 Correct 26 ms 13164 KB Output is correct
10 Correct 18 ms 9068 KB Output is correct
11 Correct 23 ms 10604 KB Output is correct
12 Correct 13 ms 6636 KB Output is correct
13 Correct 29 ms 13164 KB Output is correct
14 Correct 28 ms 13164 KB Output is correct
15 Correct 28 ms 13164 KB Output is correct
16 Correct 22 ms 10732 KB Output is correct
17 Correct 15 ms 8812 KB Output is correct
18 Correct 11 ms 6636 KB Output is correct
19 Correct 1891 ms 220780 KB Output is correct
20 Correct 1876 ms 220780 KB Output is correct
21 Correct 1832 ms 220868 KB Output is correct
22 Correct 623 ms 55712 KB Output is correct
23 Correct 601 ms 85484 KB Output is correct
24 Correct 263 ms 9840 KB Output is correct
25 Correct 1444 ms 211228 KB Output is correct
26 Correct 1640 ms 211168 KB Output is correct
27 Correct 1271 ms 202524 KB Output is correct
28 Correct 533 ms 81836 KB Output is correct
29 Correct 443 ms 47428 KB Output is correct
30 Correct 220 ms 9580 KB Output is correct
31 Correct 1614 ms 220664 KB Output is correct
32 Correct 1776 ms 221004 KB Output is correct
33 Correct 1793 ms 220808 KB Output is correct
34 Correct 524 ms 55788 KB Output is correct
35 Correct 544 ms 85612 KB Output is correct
36 Correct 253 ms 9836 KB Output is correct
37 Correct 1584 ms 220696 KB Output is correct
38 Correct 1700 ms 220932 KB Output is correct
39 Correct 1376 ms 214372 KB Output is correct
40 Correct 505 ms 82028 KB Output is correct
41 Correct 420 ms 47340 KB Output is correct
42 Correct 221 ms 9452 KB Output is correct
43 Correct 1788 ms 285772 KB Output is correct
44 Correct 1807 ms 290564 KB Output is correct
45 Correct 1951 ms 290316 KB Output is correct
46 Correct 667 ms 94428 KB Output is correct
47 Correct 704 ms 149228 KB Output is correct
48 Correct 236 ms 10664 KB Output is correct
49 Correct 1739 ms 276460 KB Output is correct
50 Correct 1640 ms 278688 KB Output is correct
51 Correct 1489 ms 264556 KB Output is correct
52 Correct 665 ms 149856 KB Output is correct
53 Correct 564 ms 85484 KB Output is correct