oj.uz

Submission #869951

# Submission time Handle Problem Language Result Execution time Memory
869951 2023-11-06T12:01:18 Z overwatch9 Examination (JOI19_examination) C++17
22 / 100
 1720 ms 440520 KB 
#include <iostream>
#include <vector>
#include <array>
#include <map>
using namespace std;
using ll = long long;
int n, q;
vector <pair <ll, ll>> ppl;
vector <array <ll, 3>> queries;
struct stree {
    #define lc v*2
    #define rc v*2+1
    vector <map <int, ll>> tree;
    vector <vector <pair <ll, ll>>> tree_pfx;
    stree (int s) {
        tree.resize(s*4);
        tree_pfx.resize(s*4);
    }
    void pushup(int v, int val) {
        tree[v][val]++;
    }
    void update(int v, int tl, int tr, int p, ll val) {
        if (tl > p || tr < p)
            return;
        if (tl == tr) {
            tree[v][val]++;
            return;
        }
        int tm = (tl + tr) / 2;
        update(lc, tl, tm, p, val);
        update(rc, tm+1, tr, p, val);
        pushup(v, val);
    }
    void build_pfx(int v, int tl, int tr) {
        int p = 0;
        tree_pfx[v].resize(tree[v].size());
        for (auto i : tree[v]) {
            tree_pfx[v][p] = i;
            if (p-1 >= 0)
                tree_pfx[v][p].second += tree_pfx[v][p-1].second;
            p++;
        }
        if (tl == tr)
            return;
        int tm = (tl + tr) / 2;
        build_pfx(lc, tl, tm);
        build_pfx(rc, tm+1, tr);
    }
    int query(int v, int tl, int tr, int l, int r, int val) {
        if (tl > r || tr < l)
            return 0;
        if (tl >= l && tr <= r) {
            if (tree_pfx[v].empty())
                return 0;
            pair <ll, ll> tp = {val, 0};
            auto x = lower_bound(tree_pfx[v].begin(), tree_pfx[v].end(), tp) - tree_pfx[v].begin();
            if (x == 0)
                return tree_pfx[v].back().second;
            else
                return tree_pfx[v].back().second - tree_pfx[v][x-1].second;
        }
        int tm = (tl + tr) / 2;
        int a = query(lc, tl, tm, l, r, val);
        int b = query(rc, tm+1, tr, l, r, val);
        return a + b;
    }
};
void subtask1() {
    for (int i = 0; i < q; i++) {
        int ans = 0;
        ll a = queries[i][0], b = queries[i][1], c = queries[i][2];
        for (int j = 0; j < n; j++) {
            if (ppl[j].first + ppl[j].second >= c && ppl[j].first >= a && ppl[j].second >= b)
                ans++;
        }
        cout << ans << '\n';
    }
}
stree tree(1e6 + 51);
void subtask2() {
    int sz = 1e6 + 50;
    for (int i = 0; i < n; i++) {
        tree.update(1, 0, sz, ppl[i].first, ppl[i].second);
    }
    tree.build_pfx(1, 0, sz);
    for (int i = 0; i < q; i++) {
        cout << tree.query(1, 0, sz, queries[i][0], sz, queries[i][1]) << '\n';
    }
}
int main() {
    cin >> n >> q;
    ppl.resize(n);
    queries.resize(q);
    for (int i = 0; i < n; i++)
        cin >> ppl[i].first >> ppl[i].second;
    for (int i = 0; i < q; i++)
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    if (n <= 3000 && q <= 3000)
        subtask1();
    else
        subtask2();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 282032 KB Output is correct
2 Correct 58 ms 281992 KB Output is correct
3 Correct 58 ms 282212 KB Output is correct
4 Correct 58 ms 282192 KB Output is correct
5 Correct 58 ms 282196 KB Output is correct
6 Correct 59 ms 282224 KB Output is correct
7 Correct 87 ms 282192 KB Output is correct
8 Correct 90 ms 282360 KB Output is correct
9 Correct 85 ms 282196 KB Output is correct
10 Correct 85 ms 282208 KB Output is correct
11 Correct 87 ms 282196 KB Output is correct
12 Correct 88 ms 282168 KB Output is correct
13 Correct 84 ms 282192 KB Output is correct
14 Correct 83 ms 282356 KB Output is correct
15 Correct 84 ms 282196 KB Output is correct
16 Correct 79 ms 282196 KB Output is correct
17 Correct 78 ms 282192 KB Output is correct
18 Correct 67 ms 282192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1693 ms 437652 KB Output is correct
2 Correct 1672 ms 440520 KB Output is correct
3 Correct 1667 ms 440148 KB Output is correct
4 Correct 414 ms 327336 KB Output is correct
5 Correct 1088 ms 399776 KB Output is correct
6 Correct 162 ms 287552 KB Output is correct
7 Correct 1667 ms 440088 KB Output is correct
8 Correct 1634 ms 439892 KB Output is correct
9 Correct 1613 ms 440264 KB Output is correct
10 Correct 844 ms 392248 KB Output is correct
11 Correct 255 ms 303096 KB Output is correct
12 Correct 147 ms 287292 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1693 ms 437652 KB Output is correct
2 Correct 1672 ms 440520 KB Output is correct
3 Correct 1667 ms 440148 KB Output is correct
4 Correct 414 ms 327336 KB Output is correct
5 Correct 1088 ms 399776 KB Output is correct
6 Correct 162 ms 287552 KB Output is correct
7 Correct 1667 ms 440088 KB Output is correct
8 Correct 1634 ms 439892 KB Output is correct
9 Correct 1613 ms 440264 KB Output is correct
10 Correct 844 ms 392248 KB Output is correct
11 Correct 255 ms 303096 KB Output is correct
12 Correct 147 ms 287292 KB Output is correct
13 Incorrect 1720 ms 440444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 282032 KB Output is correct
2 Correct 58 ms 281992 KB Output is correct
3 Correct 58 ms 282212 KB Output is correct
4 Correct 58 ms 282192 KB Output is correct
5 Correct 58 ms 282196 KB Output is correct
6 Correct 59 ms 282224 KB Output is correct
7 Correct 87 ms 282192 KB Output is correct
8 Correct 90 ms 282360 KB Output is correct
9 Correct 85 ms 282196 KB Output is correct
10 Correct 85 ms 282208 KB Output is correct
11 Correct 87 ms 282196 KB Output is correct
12 Correct 88 ms 282168 KB Output is correct
13 Correct 84 ms 282192 KB Output is correct
14 Correct 83 ms 282356 KB Output is correct
15 Correct 84 ms 282196 KB Output is correct
16 Correct 79 ms 282196 KB Output is correct
17 Correct 78 ms 282192 KB Output is correct
18 Correct 67 ms 282192 KB Output is correct
19 Correct 1693 ms 437652 KB Output is correct
20 Correct 1672 ms 440520 KB Output is correct
21 Correct 1667 ms 440148 KB Output is correct
22 Correct 414 ms 327336 KB Output is correct
23 Correct 1088 ms 399776 KB Output is correct
24 Correct 162 ms 287552 KB Output is correct
25 Correct 1667 ms 440088 KB Output is correct
26 Correct 1634 ms 439892 KB Output is correct
27 Correct 1613 ms 440264 KB Output is correct
28 Correct 844 ms 392248 KB Output is correct
29 Correct 255 ms 303096 KB Output is correct
30 Correct 147 ms 287292 KB Output is correct
31 Incorrect 1720 ms 440444 KB Output isn't correct
32 Halted 0 ms 0 KB -