oj.uz

Submission #870023

# Submission time Handle Problem Language Result Execution time Memory
870023 2023-11-06T16:23:12 Z overwatch9 Examination (JOI19_examination) C++17
2 / 100
 3000 ms 8532 KB 
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;
int n, q;
vector <pair <ll, ll>> ppl;
vector <array <ll, 4>> queries;
struct stree {
    #define lc v*2
    #define rc v*2+1
    vector <int> tree;
    stree (int s) {
        tree.resize(s*4);
    }
    void pushup(int v) {
        tree[v] = tree[lc] + tree[rc];
    }
    void update(int v, int tl, int tr, int p) {
        if (tl > p || tr < p)
            return;
        if (tl == tr) {
            tree[v]++;
            return;
        }
        int tm = (tl + tr) / 2;
        update(lc, tl, tm, p);
        update(rc, tm+1, tr, p);
        pushup(v);
    }
    int query(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l)
            return 0;
        if (tl >= l && tr <= r)
            return tree[v];
        int tm = (tl + tr) / 2;
        int a = query(lc, tl, tm, l, r);
        int b = query(rc, tm+1, tr, l, r);
        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';
    }
}
int sz = 1e5;
stree trees(sz + 1), treet(sz + 1);
bool comp(array <ll, 4> a, array <ll, 4> b) {
    return a[2] > b[2];
}
bool comp2(pair <ll, ll> a, pair <ll, ll> b) {
    return a.first + a.second > b.first + b.second;
}
void subtask23() {
    sort(queries.begin(), queries.end(), comp);
    sort(ppl.begin(), ppl.end(), comp2);
    vector <int> ans(q);
    for (int i = 0, p = 0; i < q; i++) {
        while (p < n && ppl[p].first + ppl[p].second >= queries[i][2]) {
            int s = ppl[p].first, t = ppl[p].second;
            trees.update(1, 0, sz, s);
            treet.update(1, 0, sz, t);
        }
        int satisfied_x = trees.query(1, 0, sz, queries[i][0], sz);
        int satisfied_y = treet.query(1, 0, sz, queries[i][1], sz);
        int tot = p;
        int id = queries[i][3];
        ans[id] = satisfied_x + satisfied_y - tot;
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\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];
        queries[i][3] = i;
    }
    if (n <= 3000 && q <= 3000)
        subtask1();
    else
        subtask23();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3540 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3416 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 30 ms 3928 KB Output is correct
8 Correct 29 ms 3672 KB Output is correct
9 Correct 34 ms 3676 KB Output is correct
10 Correct 29 ms 3676 KB Output is correct
11 Correct 30 ms 3716 KB Output is correct
12 Correct 29 ms 3676 KB Output is correct
13 Correct 30 ms 3676 KB Output is correct
14 Correct 29 ms 3676 KB Output is correct
15 Correct 29 ms 3676 KB Output is correct
16 Correct 22 ms 3676 KB Output is correct
17 Correct 23 ms 3672 KB Output is correct
18 Correct 12 ms 3676 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 8532 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 3044 ms 8532 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 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3540 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 3416 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 30 ms 3928 KB Output is correct
8 Correct 29 ms 3672 KB Output is correct
9 Correct 34 ms 3676 KB Output is correct
10 Correct 29 ms 3676 KB Output is correct
11 Correct 30 ms 3716 KB Output is correct
12 Correct 29 ms 3676 KB Output is correct
13 Correct 30 ms 3676 KB Output is correct
14 Correct 29 ms 3676 KB Output is correct
15 Correct 29 ms 3676 KB Output is correct
16 Correct 22 ms 3676 KB Output is correct
17 Correct 23 ms 3672 KB Output is correct
18 Correct 12 ms 3676 KB Output is correct
19 Execution timed out 3044 ms 8532 KB Time limit exceeded
20 Halted 0 ms 0 KB -