oj.uz

Submission #715880

# Submission time Handle Problem Language Result Execution time Memory
715880 2023-03-28T09:56:11 Z ismayil Examination (JOI19_examination) C++17
41 / 100
 319 ms 14152 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 1e5;
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;
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>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;
        events.push_back({x, y, max(x + y, z), i, 1});
    }
    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(i.y, 1);
            X.update(i.x, 1);
            cnt++;
        }else{
            ans[i.idx] = Y.query(i.y, MAX) + X.query(i.x, MAX) - cnt;
        }
    }
    for (int i = 0; i < m; i++) cout<<ans[i]<<endl;
}
signed main(){
    
    cin>>n>>m;
    solve();
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 1 ms 1832 KB Output is correct
4 Runtime error 3 ms 3540 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 12232 KB Output is correct
2 Correct 290 ms 12984 KB Output is correct
3 Correct 265 ms 12932 KB Output is correct
4 Correct 294 ms 12844 KB Output is correct
5 Correct 242 ms 12952 KB Output is correct
6 Correct 212 ms 12976 KB Output is correct
7 Correct 280 ms 12872 KB Output is correct
8 Correct 319 ms 12868 KB Output is correct
9 Correct 261 ms 13100 KB Output is correct
10 Correct 258 ms 13016 KB Output is correct
11 Correct 244 ms 13272 KB Output is correct
12 Correct 222 ms 12980 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 12232 KB Output is correct
2 Correct 290 ms 12984 KB Output is correct
3 Correct 265 ms 12932 KB Output is correct
4 Correct 294 ms 12844 KB Output is correct
5 Correct 242 ms 12952 KB Output is correct
6 Correct 212 ms 12976 KB Output is correct
7 Correct 280 ms 12872 KB Output is correct
8 Correct 319 ms 12868 KB Output is correct
9 Correct 261 ms 13100 KB Output is correct
10 Correct 258 ms 13016 KB Output is correct
11 Correct 244 ms 13272 KB Output is correct
12 Correct 222 ms 12980 KB Output is correct
13 Correct 301 ms 13364 KB Output is correct
14 Correct 285 ms 14040 KB Output is correct
15 Correct 273 ms 13932 KB Output is correct
16 Correct 268 ms 13592 KB Output is correct
17 Correct 267 ms 13616 KB Output is correct
18 Correct 213 ms 12964 KB Output is correct
19 Correct 281 ms 14064 KB Output is correct
20 Correct 312 ms 14152 KB Output is correct
21 Correct 289 ms 14076 KB Output is correct
22 Correct 281 ms 13460 KB Output is correct
23 Correct 243 ms 13476 KB Output is correct
24 Correct 217 ms 12948 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 1 ms 1832 KB Output is correct
4 Runtime error 3 ms 3540 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -