oj.uz

Submission #1048452

# Submission time Handle Problem Language Result Execution time Memory
1048452 2024-08-08T07:42:13 Z matere Examination (JOI19_examination) C++14
20 / 100
 275 ms 26640 KB 
#include<bits/stdc++.h>
using namespace std;
int n,q;
pair<int,int>a[100005];
vector<int>tree[400005];
void build(int v,int tl,int tr){
    for(int i=tl;i<=tr;i++) tree[v].push_back(a[i].second);
    sort(tree[v].begin(),tree[v].end());
    if(tl==tr) return;
    int mid=(tl+tr)/2;
    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);
}
int sum(int v,int tl,int tr,int l,int r,int val){
    if(l<=tl and tr<=r){
        int mr=lower_bound(tree[v].begin(),tree[v].end(),val)-tree[v].begin();
        // cout<<mr<<endl;
        return tree[v].size()-mr;
    }
    if(l>tr or tl>r){
        return 0;
    }
    int mid=(tl+tr)/2;
    return sum(v*2,tl,mid,l,r,val)+sum(v*2+1,mid+1,tr,l,r,val);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1);
    build(1,1,n);
    int x,y,z;
    for(int i=1;i<=q;i++){
        int ans=0;
        cin>>x>>y>>z;
        int l=0,r=n+1;
        while(l+1<r){
            int mid=(l+r)/2;
            if(a[mid].first<x) l=mid;
            else r=mid;
        }
        if(r==n+1) cout<<0<<endl;
        else cout<<sum(1,1,n,r,n,y)<<endl;
    }
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:37:13: warning: unused variable 'ans' [-Wunused-variable]
   37 |         int ans=0;
      |             ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 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 252 ms 25828 KB Output is correct
2 Correct 255 ms 26464 KB Output is correct
3 Correct 264 ms 26480 KB Output is correct
4 Correct 222 ms 25652 KB Output is correct
5 Correct 180 ms 25556 KB Output is correct
6 Correct 148 ms 25060 KB Output is correct
7 Correct 260 ms 26580 KB Output is correct
8 Correct 237 ms 26580 KB Output is correct
9 Correct 226 ms 26320 KB Output is correct
10 Correct 141 ms 25420 KB Output is correct
11 Correct 174 ms 25556 KB Output is correct
12 Correct 128 ms 24784 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 25828 KB Output is correct
2 Correct 255 ms 26464 KB Output is correct
3 Correct 264 ms 26480 KB Output is correct
4 Correct 222 ms 25652 KB Output is correct
5 Correct 180 ms 25556 KB Output is correct
6 Correct 148 ms 25060 KB Output is correct
7 Correct 260 ms 26580 KB Output is correct
8 Correct 237 ms 26580 KB Output is correct
9 Correct 226 ms 26320 KB Output is correct
10 Correct 141 ms 25420 KB Output is correct
11 Correct 174 ms 25556 KB Output is correct
12 Correct 128 ms 24784 KB Output is correct
13 Incorrect 275 ms 26640 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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