oj.uz

Submission #886981

# Submission time Handle Problem Language Result Execution time Memory
886981 2023-12-13T11:27:27 Z imarn Examination (JOI19_examination) C++14
20 / 100
 555 ms 51516 KB 
#include "bits/stdc++.h"
#define f first
#define s second
#define ll int
#define pb push_back
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
using namespace std;
const int N=1e5+5;
struct query{
    int i,x,y,z;
    bool operator<(const query &o)const{return x>o.x;}
};
struct fenwick{
    vector<int>v,fw;
    void build(){
        fw.resize(v.size()+1,0);
    }
    void upd(int i){
        i = upper_bound(all(v),i)-v.begin();
        for(;i<sz(fw);i+=i&-i)fw[i]++;
    }
    int qr(int i,int res=0){
        i = upper_bound(all(v),i)-v.begin();
        for(;i;i-=i&-i)res+=fw[i];
        return res;
    }
}t[4*N];
pii a[N],b[N];
int c[N];
void build(int i,int l,int r){
    if(l==r){
        t[i].v.pb(a[l].s);t[i].build();
        return;
    }int m=(l+r)>>1;
    build(2*i,l,m);build(2*i+1,m+1,r);
    int li=0,ri=0;
    while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
        if(t[2*i].v[li]<t[2*i+1].v[ri])t[i].v.pb(t[2*i].v[li++]);
        else t[i].v.pb(t[2*i+1].v[ri++]);
    }while(li<t[2*i].v.size())t[i].v.pb(t[2*i].v[li++]);
    while(ri<t[2*i+1].v.size())t[i].v.pb(t[2*i+1].v[ri++]);
    t[i].build();
}
void upd(int i,int l,int r,int idx,int v){
    if(r<idx||l>idx)return;
    if(l==r)return void(t[i].upd(v));
    int m=(l+r)>>1;
    upd(2*i,l,m,idx,v);upd(2*i+1,m+1,r,idx,v);
    t[i].upd(v);
}
int qr(int i,int l,int r,int tl,int tr,int v){
    if(r<tl||l>tr)return 0;
    if(r<=tr&&l>=tl){
        return t[i].qr(v);
    }int m=(l+r)>>1;
    return qr(2*i,l,m,tl,tr,v)+qr(2*i+1,m+1,r,tl,tr,v);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>b[i].f>>b[i].s,a[i]={b[i].s,b[i].f+b[i].s},c[i]=b[i].s;
    sort(b+1,b+1+n,greater<pii>()),sort(a+1,a+1+n);build(1,1,n);sort(c+1,c+n+1);
    query qq[q];
    for(int i=0;i<q;i++)cin>>qq[i].x>>qq[i].y>>qq[i].z,qq[i].i=i;
    sort(qq,qq+q);
    int ans[q];int j=1;
    for(int i=0;i<q;i++){
        while(j<=n&&b[j].f>=qq[i].x){
            int id=lower_bound(c+1,c+n+1,b[j].s)-c;
            upd(1,1,n,id,a[id].s);j++;
        }int id=lower_bound(c+1,c+1+n,qq[i].y)-c;
        ans[qq[i].i] = qr(1,1,n,id,n,INT_MAX)-qr(1,1,n,id,n,qq[i].z-1);
    }for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}

Compilation message

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:39:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
      |           ~~^~~~~~~~~~~~~~~~
examination.cpp:39:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
      |                               ~~^~~~~~~~~~~~~~~~~~
examination.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     }while(li<t[2*i].v.size())t[i].v.pb(t[2*i].v[li++]);
      |            ~~^~~~~~~~~~~~~~~~
examination.cpp:43:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while(ri<t[2*i+1].v.size())t[i].v.pb(t[2*i+1].v[ri++]);
      |           ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20932 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 11 ms 21852 KB Output is correct
8 Correct 11 ms 21852 KB Output is correct
9 Correct 11 ms 21892 KB Output is correct
10 Incorrect 9 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 51020 KB Output is correct
2 Correct 474 ms 51340 KB Output is correct
3 Correct 477 ms 50956 KB Output is correct
4 Correct 189 ms 50412 KB Output is correct
5 Correct 378 ms 50336 KB Output is correct
6 Correct 162 ms 49560 KB Output is correct
7 Correct 476 ms 51252 KB Output is correct
8 Correct 470 ms 50988 KB Output is correct
9 Correct 455 ms 50892 KB Output is correct
10 Correct 276 ms 50220 KB Output is correct
11 Correct 155 ms 50076 KB Output is correct
12 Correct 123 ms 49232 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 51020 KB Output is correct
2 Correct 474 ms 51340 KB Output is correct
3 Correct 477 ms 50956 KB Output is correct
4 Correct 189 ms 50412 KB Output is correct
5 Correct 378 ms 50336 KB Output is correct
6 Correct 162 ms 49560 KB Output is correct
7 Correct 476 ms 51252 KB Output is correct
8 Correct 470 ms 50988 KB Output is correct
9 Correct 455 ms 50892 KB Output is correct
10 Correct 276 ms 50220 KB Output is correct
11 Correct 155 ms 50076 KB Output is correct
12 Correct 123 ms 49232 KB Output is correct
13 Incorrect 555 ms 51516 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20824 KB Output is correct
2 Correct 4 ms 20828 KB Output is correct
3 Correct 4 ms 20932 KB Output is correct
4 Correct 5 ms 20828 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 4 ms 20828 KB Output is correct
7 Correct 11 ms 21852 KB Output is correct
8 Correct 11 ms 21852 KB Output is correct
9 Correct 11 ms 21892 KB Output is correct
10 Incorrect 9 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -