oj.uz

Submission #330888

# Submission time Handle Problem Language Result Execution time Memory
330888 2020-11-26T20:12:14 Z 12tqian Examination (JOI19_examination) C++17
43 / 100
 2303 ms 279952 KB 
#include<bits/stdc++.h>
using namespace std;
const int SZ = (1 << 17);
// [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-ndexed 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 3 ms 3436 KB Output is correct
2 Correct 3 ms 3584 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 3 ms 3436 KB Output is correct
5 Correct 3 ms 3436 KB Output is correct
6 Correct 3 ms 3436 KB Output is correct
7 Correct 39 ms 11628 KB Output is correct
8 Correct 37 ms 11756 KB Output is correct
9 Correct 37 ms 11756 KB Output is correct
10 Correct 21 ms 6508 KB Output is correct
11 Correct 26 ms 8556 KB Output is correct
12 Correct 12 ms 3564 KB Output is correct
13 Correct 39 ms 11756 KB Output is correct
14 Correct 47 ms 11756 KB Output is correct
15 Correct 39 ms 11756 KB Output is correct
16 Correct 25 ms 8684 KB Output is correct
17 Correct 19 ms 6252 KB Output is correct
18 Correct 10 ms 3436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2201 ms 279392 KB Output is correct
2 Correct 2210 ms 279460 KB Output is correct
3 Correct 2175 ms 279192 KB Output is correct
4 Correct 778 ms 64748 KB Output is correct
5 Correct 790 ms 102124 KB Output is correct
6 Correct 323 ms 6892 KB Output is correct
7 Correct 1816 ms 267060 KB Output is correct
8 Correct 2003 ms 267112 KB Output is correct
9 Correct 1691 ms 256204 KB Output is correct
10 Correct 759 ms 97644 KB Output is correct
11 Correct 589 ms 53868 KB Output is correct
12 Correct 286 ms 6636 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2201 ms 279392 KB Output is correct
2 Correct 2210 ms 279460 KB Output is correct
3 Correct 2175 ms 279192 KB Output is correct
4 Correct 778 ms 64748 KB Output is correct
5 Correct 790 ms 102124 KB Output is correct
6 Correct 323 ms 6892 KB Output is correct
7 Correct 1816 ms 267060 KB Output is correct
8 Correct 2003 ms 267112 KB Output is correct
9 Correct 1691 ms 256204 KB Output is correct
10 Correct 759 ms 97644 KB Output is correct
11 Correct 589 ms 53868 KB Output is correct
12 Correct 286 ms 6636 KB Output is correct
13 Correct 2212 ms 279492 KB Output is correct
14 Correct 2220 ms 279916 KB Output is correct
15 Correct 2303 ms 279712 KB Output is correct
16 Correct 700 ms 65488 KB Output is correct
17 Correct 806 ms 102900 KB Output is correct
18 Correct 313 ms 7368 KB Output is correct
19 Correct 2103 ms 279788 KB Output is correct
20 Correct 2214 ms 279952 KB Output is correct
21 Correct 1844 ms 271724 KB Output is correct
22 Correct 729 ms 97980 KB Output is correct
23 Correct 586 ms 54380 KB Output is correct
24 Correct 280 ms 7020 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 3 ms 3584 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 3 ms 3436 KB Output is correct
5 Correct 3 ms 3436 KB Output is correct
6 Correct 3 ms 3436 KB Output is correct
7 Correct 39 ms 11628 KB Output is correct
8 Correct 37 ms 11756 KB Output is correct
9 Correct 37 ms 11756 KB Output is correct
10 Correct 21 ms 6508 KB Output is correct
11 Correct 26 ms 8556 KB Output is correct
12 Correct 12 ms 3564 KB Output is correct
13 Correct 39 ms 11756 KB Output is correct
14 Correct 47 ms 11756 KB Output is correct
15 Correct 39 ms 11756 KB Output is correct
16 Correct 25 ms 8684 KB Output is correct
17 Correct 19 ms 6252 KB Output is correct
18 Correct 10 ms 3436 KB Output is correct
19 Correct 2201 ms 279392 KB Output is correct
20 Correct 2210 ms 279460 KB Output is correct
21 Correct 2175 ms 279192 KB Output is correct
22 Correct 778 ms 64748 KB Output is correct
23 Correct 790 ms 102124 KB Output is correct
24 Correct 323 ms 6892 KB Output is correct
25 Correct 1816 ms 267060 KB Output is correct
26 Correct 2003 ms 267112 KB Output is correct
27 Correct 1691 ms 256204 KB Output is correct
28 Correct 759 ms 97644 KB Output is correct
29 Correct 589 ms 53868 KB Output is correct
30 Correct 286 ms 6636 KB Output is correct
31 Correct 2212 ms 279492 KB Output is correct
32 Correct 2220 ms 279916 KB Output is correct
33 Correct 2303 ms 279712 KB Output is correct
34 Correct 700 ms 65488 KB Output is correct
35 Correct 806 ms 102900 KB Output is correct
36 Correct 313 ms 7368 KB Output is correct
37 Correct 2103 ms 279788 KB Output is correct
38 Correct 2214 ms 279952 KB Output is correct
39 Correct 1844 ms 271724 KB Output is correct
40 Correct 729 ms 97980 KB Output is correct
41 Correct 586 ms 54380 KB Output is correct
42 Correct 280 ms 7020 KB Output is correct
43 Runtime error 760 ms 89116 KB Execution killed with signal 7 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -