oj.uz

Submission #715906

# Submission time Handle Problem Language Result Execution time Memory
715906 2023-03-28T11:51:27 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 1012 ms 42460 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 5e5;
struct fenwick_tree{
    int bit[MAX + 1] = {0};
    void update(int pos, int val){
        for(int i = pos; i <= MAX; i = i | (i + 1)){
            bit[i] += val;
        }
    }
    int query(int pos){
        int res = 0;
        for(int i = pos; i >= 0; i = (i & (i + 1)) - 1){
            res += bit[i];
        }
        return res;
    }
    int query(int l, int r){
        if(l == 0) return query(r);
        return query(r) - query(l - 1);
    }
};
struct event{
    int x, y, z, idx, type;
    bool operator<(event other){
        if(z == other.z) return type < other.type;
        return z > other.z;
    }
};
int n, m;
void solve(){
    vector<event> events;
    map<int, int> mm;
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        mm[x]; mm[y];
        events.push_back({x, y, x + y, -1, 0});
    }
    for(int i = 0; i < m; i++){
        int x, y, z;
        cin>>x>>y>>z;
        mm[x]; mm[y];
        events.push_back({x, y, max(x + y, z), i, 1});
    }
    int idx = 0;
    for(auto& i : mm) i.second = idx++;
    sort(events.begin(), events.end());
    int ans[m];
    fenwick_tree X, Y;
    int cnt = 0;
    for (auto i : events)
    {
        if(i.type == 0){
            Y.update(mm[i.y], 1);
            X.update(mm[i.x], 1);
            cnt++;
        }else{
            ans[i.idx] = Y.query(mm[i.y], MAX) + X.query(mm[i.x], MAX) - cnt;
        }
    }
    for (int i = 0; i < m; i++) cout<<ans[i]<<endl;
}
signed main(){
    
    cin>>n>>m;
    solve();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 5 ms 8128 KB Output is correct
3 Correct 4 ms 8020 KB Output is correct
4 Correct 5 ms 8104 KB Output is correct
5 Correct 4 ms 8020 KB Output is correct
6 Correct 5 ms 8020 KB Output is correct
7 Correct 24 ms 9128 KB Output is correct
8 Correct 19 ms 9140 KB Output is correct
9 Correct 22 ms 9128 KB Output is correct
10 Correct 15 ms 8752 KB Output is correct
11 Correct 18 ms 8808 KB Output is correct
12 Correct 11 ms 8500 KB Output is correct
13 Correct 19 ms 9112 KB Output is correct
14 Correct 19 ms 9160 KB Output is correct
15 Correct 19 ms 9116 KB Output is correct
16 Correct 15 ms 8764 KB Output is correct
17 Correct 14 ms 8780 KB Output is correct
18 Correct 10 ms 8544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 24268 KB Output is correct
2 Correct 546 ms 24140 KB Output is correct
3 Correct 567 ms 24132 KB Output is correct
4 Correct 399 ms 22968 KB Output is correct
5 Correct 368 ms 22908 KB Output is correct
6 Correct 225 ms 18508 KB Output is correct
7 Correct 495 ms 24108 KB Output is correct
8 Correct 551 ms 24040 KB Output is correct
9 Correct 478 ms 23916 KB Output is correct
10 Correct 330 ms 22992 KB Output is correct
11 Correct 344 ms 22992 KB Output is correct
12 Correct 220 ms 18456 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 24268 KB Output is correct
2 Correct 546 ms 24140 KB Output is correct
3 Correct 567 ms 24132 KB Output is correct
4 Correct 399 ms 22968 KB Output is correct
5 Correct 368 ms 22908 KB Output is correct
6 Correct 225 ms 18508 KB Output is correct
7 Correct 495 ms 24108 KB Output is correct
8 Correct 551 ms 24040 KB Output is correct
9 Correct 478 ms 23916 KB Output is correct
10 Correct 330 ms 22992 KB Output is correct
11 Correct 344 ms 22992 KB Output is correct
12 Correct 220 ms 18456 KB Output is correct
13 Correct 537 ms 24308 KB Output is correct
14 Correct 552 ms 24100 KB Output is correct
15 Correct 560 ms 24196 KB Output is correct
16 Correct 389 ms 22992 KB Output is correct
17 Correct 385 ms 22944 KB Output is correct
18 Correct 227 ms 18468 KB Output is correct
19 Correct 555 ms 24144 KB Output is correct
20 Correct 531 ms 24284 KB Output is correct
21 Correct 522 ms 24156 KB Output is correct
22 Correct 332 ms 22924 KB Output is correct
23 Correct 342 ms 22944 KB Output is correct
24 Correct 218 ms 18516 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Correct 5 ms 8128 KB Output is correct
3 Correct 4 ms 8020 KB Output is correct
4 Correct 5 ms 8104 KB Output is correct
5 Correct 4 ms 8020 KB Output is correct
6 Correct 5 ms 8020 KB Output is correct
7 Correct 24 ms 9128 KB Output is correct
8 Correct 19 ms 9140 KB Output is correct
9 Correct 22 ms 9128 KB Output is correct
10 Correct 15 ms 8752 KB Output is correct
11 Correct 18 ms 8808 KB Output is correct
12 Correct 11 ms 8500 KB Output is correct
13 Correct 19 ms 9112 KB Output is correct
14 Correct 19 ms 9160 KB Output is correct
15 Correct 19 ms 9116 KB Output is correct
16 Correct 15 ms 8764 KB Output is correct
17 Correct 14 ms 8780 KB Output is correct
18 Correct 10 ms 8544 KB Output is correct
19 Correct 524 ms 24268 KB Output is correct
20 Correct 546 ms 24140 KB Output is correct
21 Correct 567 ms 24132 KB Output is correct
22 Correct 399 ms 22968 KB Output is correct
23 Correct 368 ms 22908 KB Output is correct
24 Correct 225 ms 18508 KB Output is correct
25 Correct 495 ms 24108 KB Output is correct
26 Correct 551 ms 24040 KB Output is correct
27 Correct 478 ms 23916 KB Output is correct
28 Correct 330 ms 22992 KB Output is correct
29 Correct 344 ms 22992 KB Output is correct
30 Correct 220 ms 18456 KB Output is correct
31 Correct 537 ms 24308 KB Output is correct
32 Correct 552 ms 24100 KB Output is correct
33 Correct 560 ms 24196 KB Output is correct
34 Correct 389 ms 22992 KB Output is correct
35 Correct 385 ms 22944 KB Output is correct
36 Correct 227 ms 18468 KB Output is correct
37 Correct 555 ms 24144 KB Output is correct
38 Correct 531 ms 24284 KB Output is correct
39 Correct 522 ms 24156 KB Output is correct
40 Correct 332 ms 22924 KB Output is correct
41 Correct 342 ms 22944 KB Output is correct
42 Correct 218 ms 18516 KB Output is correct
43 Correct 1012 ms 42432 KB Output is correct
44 Correct 917 ms 42328 KB Output is correct
45 Correct 914 ms 42252 KB Output is correct
46 Correct 492 ms 29792 KB Output is correct
47 Correct 484 ms 29708 KB Output is correct
48 Correct 231 ms 18500 KB Output is correct
49 Correct 950 ms 42440 KB Output is correct
50 Correct 942 ms 42460 KB Output is correct
51 Correct 909 ms 42276 KB Output is correct
52 Correct 491 ms 29632 KB Output is correct
53 Correct 440 ms 29664 KB Output is correct