oj.uz

Submission #715236

# Submission time Handle Problem Language Result Execution time Memory
715236 2023-03-26T08:52:43 Z ismayil Examination (JOI19_examination) C++17
20 / 100
 295 ms 4428 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5;
int bit[MAX + 1];
void update(int pos, int val){
    for(int i = pos; i <= MAX; i = i | (i + 1)){
        bit[i] += val;
    }
}
int ask(int pos){
    int res = 0;
    for(int i = pos; i >= 0; i = (i & (i + 1)) - 1){
        res += bit[i];
    }
    return res;
}
int ask(int l, int r){
    if(l == 0) return ask(r);
    return ask(r) - ask(l - 1);
}
struct query{
    int x, y, idx;
    bool operator<(query other){
        return x < other.x;
    }
};
int main(){
    int n, m;
    cin>>n>>m;
    vector<pair<int, int>> p;
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        p.push_back({x, y});
    }
    sort(p.begin(), p.end());
    vector<query> queries;
    for(int i = 0; i < m; i++){
        int x, y, z;
        cin>>x>>y>>z;
        queries.push_back({x, y, i});
    }
    sort(queries.begin(), queries.end());
    int ans[m];
    int idx = n - 1;
    for (int i = m - 1; i >= 0; i--)
    {
        while(idx >= 0 && queries[i].x <= p[idx].first){
            update(p[idx].second, 1);
            idx--;
        }
        ans[queries[i].idx] = ask(queries[i].y, MAX);
    }
    for (int i = 0; i < m; i++) cout<<ans[i]<<endl;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 4252 KB Output is correct
2 Correct 245 ms 4272 KB Output is correct
3 Correct 295 ms 4324 KB Output is correct
4 Correct 223 ms 3924 KB Output is correct
5 Correct 245 ms 4360 KB Output is correct
6 Correct 206 ms 4008 KB Output is correct
7 Correct 241 ms 4344 KB Output is correct
8 Correct 276 ms 4336 KB Output is correct
9 Correct 235 ms 4284 KB Output is correct
10 Correct 229 ms 4352 KB Output is correct
11 Correct 227 ms 3756 KB Output is correct
12 Correct 193 ms 3624 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 4252 KB Output is correct
2 Correct 245 ms 4272 KB Output is correct
3 Correct 295 ms 4324 KB Output is correct
4 Correct 223 ms 3924 KB Output is correct
5 Correct 245 ms 4360 KB Output is correct
6 Correct 206 ms 4008 KB Output is correct
7 Correct 241 ms 4344 KB Output is correct
8 Correct 276 ms 4336 KB Output is correct
9 Correct 235 ms 4284 KB Output is correct
10 Correct 229 ms 4352 KB Output is correct
11 Correct 227 ms 3756 KB Output is correct
12 Correct 193 ms 3624 KB Output is correct
13 Incorrect 271 ms 4428 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -