oj.uz

Submission #512836

# Submission time Handle Problem Language Result Execution time Memory
512836 2022-01-16T18:48:34 Z couplefire Examination (JOI19_examination) C++17
100 / 100
 1112 ms 94760 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define pii pair<int, int>
#define f first
#define s second

const int N = 100005;

int n, q, m;
ordered_set bit[N];
map<int, int> mp;
pii arr[N];
pair<pii, pii> queries[N];
int ans[N];

void upd(int x, int y){
    for(; x<N; x = (x|(x+1)))
        bit[x].insert(y);
}

int query(int x, int y){
    int res = 0;
    for(; x>=0; x = (x&(x+1))-1)
        res += bit[x].order_of_key(y+1);
    return res;
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    vector<int> tmp;
    for(int i = 0; i<n; ++i)
        cin >> arr[i].f >> arr[i].s, tmp.push_back(arr[i].f);
    sort(arr, arr+n, [&](pii a, pii b){return a.f+a.s<b.f+b.s;});
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    m = tmp.size();
    for(int i = 0; i<m; ++i)
        mp[tmp[i]] = i;
    for(int i = 0; i<q; ++i)
        cin >> queries[i].s.f >> queries[i].s.s >> queries[i].f.f, queries[i].f.s = i;
    sort(queries, queries+q);
    for(int i = q-1, j = n-1; i>=0; --i){
        while(j>=0 && arr[j].f+arr[j].s>=queries[i].f.f)
            upd(m-1-mp[arr[j].f], 1e9-arr[j].s), --j;
        int id = lower_bound(tmp.begin(), tmp.end(), queries[i].s.f)-tmp.begin();
        ans[queries[i].f.s] = query(m-1-id, 1e9-queries[i].s.s);
    }
    for(int i = 0; i<q; ++i)
        cout << ans[i] << '\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8044 KB Output is correct
2 Correct 7 ms 8132 KB Output is correct
3 Correct 6 ms 8140 KB Output is correct
4 Correct 6 ms 8140 KB Output is correct
5 Correct 7 ms 8140 KB Output is correct
6 Correct 6 ms 8096 KB Output is correct
7 Correct 17 ms 10060 KB Output is correct
8 Correct 18 ms 10060 KB Output is correct
9 Correct 26 ms 10060 KB Output is correct
10 Correct 18 ms 10096 KB Output is correct
11 Correct 22 ms 10540 KB Output is correct
12 Correct 19 ms 10452 KB Output is correct
13 Correct 17 ms 10060 KB Output is correct
14 Correct 18 ms 10024 KB Output is correct
15 Correct 17 ms 10060 KB Output is correct
16 Correct 21 ms 10612 KB Output is correct
17 Correct 17 ms 10048 KB Output is correct
18 Correct 18 ms 10680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1094 ms 60180 KB Output is correct
2 Correct 1063 ms 60108 KB Output is correct
3 Correct 1081 ms 60048 KB Output is correct
4 Correct 791 ms 59212 KB Output is correct
5 Correct 761 ms 86168 KB Output is correct
6 Correct 702 ms 85408 KB Output is correct
7 Correct 944 ms 59948 KB Output is correct
8 Correct 935 ms 59892 KB Output is correct
9 Correct 817 ms 59768 KB Output is correct
10 Correct 993 ms 93264 KB Output is correct
11 Correct 511 ms 59004 KB Output is correct
12 Correct 938 ms 92260 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1094 ms 60180 KB Output is correct
2 Correct 1063 ms 60108 KB Output is correct
3 Correct 1081 ms 60048 KB Output is correct
4 Correct 791 ms 59212 KB Output is correct
5 Correct 761 ms 86168 KB Output is correct
6 Correct 702 ms 85408 KB Output is correct
7 Correct 944 ms 59948 KB Output is correct
8 Correct 935 ms 59892 KB Output is correct
9 Correct 817 ms 59768 KB Output is correct
10 Correct 993 ms 93264 KB Output is correct
11 Correct 511 ms 59004 KB Output is correct
12 Correct 938 ms 92260 KB Output is correct
13 Correct 947 ms 60356 KB Output is correct
14 Correct 1112 ms 60348 KB Output is correct
15 Correct 1035 ms 60064 KB Output is correct
16 Correct 580 ms 59724 KB Output is correct
17 Correct 708 ms 86536 KB Output is correct
18 Correct 683 ms 85372 KB Output is correct
19 Correct 918 ms 60488 KB Output is correct
20 Correct 1008 ms 60384 KB Output is correct
21 Correct 832 ms 60372 KB Output is correct
22 Correct 946 ms 93180 KB Output is correct
23 Correct 539 ms 58996 KB Output is correct
24 Correct 897 ms 92368 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8044 KB Output is correct
2 Correct 7 ms 8132 KB Output is correct
3 Correct 6 ms 8140 KB Output is correct
4 Correct 6 ms 8140 KB Output is correct
5 Correct 7 ms 8140 KB Output is correct
6 Correct 6 ms 8096 KB Output is correct
7 Correct 17 ms 10060 KB Output is correct
8 Correct 18 ms 10060 KB Output is correct
9 Correct 26 ms 10060 KB Output is correct
10 Correct 18 ms 10096 KB Output is correct
11 Correct 22 ms 10540 KB Output is correct
12 Correct 19 ms 10452 KB Output is correct
13 Correct 17 ms 10060 KB Output is correct
14 Correct 18 ms 10024 KB Output is correct
15 Correct 17 ms 10060 KB Output is correct
16 Correct 21 ms 10612 KB Output is correct
17 Correct 17 ms 10048 KB Output is correct
18 Correct 18 ms 10680 KB Output is correct
19 Correct 1094 ms 60180 KB Output is correct
20 Correct 1063 ms 60108 KB Output is correct
21 Correct 1081 ms 60048 KB Output is correct
22 Correct 791 ms 59212 KB Output is correct
23 Correct 761 ms 86168 KB Output is correct
24 Correct 702 ms 85408 KB Output is correct
25 Correct 944 ms 59948 KB Output is correct
26 Correct 935 ms 59892 KB Output is correct
27 Correct 817 ms 59768 KB Output is correct
28 Correct 993 ms 93264 KB Output is correct
29 Correct 511 ms 59004 KB Output is correct
30 Correct 938 ms 92260 KB Output is correct
31 Correct 947 ms 60356 KB Output is correct
32 Correct 1112 ms 60348 KB Output is correct
33 Correct 1035 ms 60064 KB Output is correct
34 Correct 580 ms 59724 KB Output is correct
35 Correct 708 ms 86536 KB Output is correct
36 Correct 683 ms 85372 KB Output is correct
37 Correct 918 ms 60488 KB Output is correct
38 Correct 1008 ms 60384 KB Output is correct
39 Correct 832 ms 60372 KB Output is correct
40 Correct 946 ms 93180 KB Output is correct
41 Correct 539 ms 58996 KB Output is correct
42 Correct 897 ms 92368 KB Output is correct
43 Correct 905 ms 62656 KB Output is correct
44 Correct 926 ms 62544 KB Output is correct
45 Correct 1054 ms 62504 KB Output is correct
46 Correct 559 ms 61060 KB Output is correct
47 Correct 716 ms 87852 KB Output is correct
48 Correct 646 ms 85180 KB Output is correct
49 Correct 869 ms 62652 KB Output is correct
50 Correct 834 ms 62552 KB Output is correct
51 Correct 795 ms 62388 KB Output is correct
52 Correct 1000 ms 94760 KB Output is correct
53 Correct 498 ms 60024 KB Output is correct