oj.uz

Submission #330832

# Submission time Handle Problem Language Result Execution time Memory
330832 2020-11-26T17:17:57 Z 12tqian Examination (JOI19_examination) C++17
2 / 100
 3000 ms 658536 KB 
#include<bits/stdc++.h>
const int SZ = (1 << 30);
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 Node2D {
    Node<T> seg; 
    Node2D* c[2];
    Node2D() { c[0] = c[1] = NULL; }
    void upd(int x, int y, T v, int L = 0, int R = SZ - 1) { // add v
        if (L == x && R == x) { seg.upd(y, v); return; }
        int M = (L + R) / 2;
        if (x <= M) {
            if (!c[0]) c[0] = new Node2D();
            c[0]->upd(x, y, v, L, M);
        } else {
            if (!c[1]) c[1] = new Node2D();
            c[1]->upd(x, y, v, M + 1, R);
        }
        seg.upd(y, v); // only for addition
        // seg.update_2d(y, (c[0] ? & c[0]->seg : NULL), (c[1] ? & c[1]->seg : NULL));
    }
    T query(int x1, int x2, int y1, int y2, int L = 0, int R = SZ - 1) { // query sum of rectangle
        if (x1 <= L && R <= x2) return seg.query(y1, y2);
        if (x2 < L || R < x1) return 0;
        int M = (L + R) / 2; 
        T res = 0;
        if (c[0]) res += c[0]->query(x1, x2, y1, y2, L, M);
        if (c[1]) res += c[1]->query(x1, x2, y1, y2, M + 1, R);
        return res;
    }
};
int main() {
    using namespace std;
    typedef long long ll;
    int n, q; cin >> n >> q;
    vector<array<int, 2>> v(n);
    for (int i = 0; i < n; i++) 
        cin >> v[i][0] >> 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];
    }
    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];
    });
    Node2D<ll> 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(v[qv][0], v[qv][1], 1);
        }
        ans[queries[i][0]] = seg.query(queries[i][1], SZ - 1, 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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 157 ms 84716 KB Output is correct
8 Correct 155 ms 84588 KB Output is correct
9 Correct 159 ms 84588 KB Output is correct
10 Correct 102 ms 58988 KB Output is correct
11 Correct 110 ms 57964 KB Output is correct
12 Correct 23 ms 492 KB Output is correct
13 Correct 154 ms 84588 KB Output is correct
14 Correct 161 ms 84736 KB Output is correct
15 Correct 156 ms 84716 KB Output is correct
16 Correct 110 ms 57196 KB Output is correct
17 Correct 107 ms 58112 KB Output is correct
18 Correct 19 ms 492 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3105 ms 658536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3105 ms 658536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 157 ms 84716 KB Output is correct
8 Correct 155 ms 84588 KB Output is correct
9 Correct 159 ms 84588 KB Output is correct
10 Correct 102 ms 58988 KB Output is correct
11 Correct 110 ms 57964 KB Output is correct
12 Correct 23 ms 492 KB Output is correct
13 Correct 154 ms 84588 KB Output is correct
14 Correct 161 ms 84736 KB Output is correct
15 Correct 156 ms 84716 KB Output is correct
16 Correct 110 ms 57196 KB Output is correct
17 Correct 107 ms 58112 KB Output is correct
18 Correct 19 ms 492 KB Output is correct
19 Execution timed out 3105 ms 658536 KB Time limit exceeded
20 Halted 0 ms 0 KB -