oj.uz

Submission #886987

# Submission time Handle Problem Language Result Execution time Memory
886987 2023-12-13T11:43:59 Z imarn Examination (JOI19_examination) C++14
20 / 100
 522 ms 55148 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{
    ll i,x,y,z;
    bool operator<(const query &o)const{return x>o.x;}
};
struct fenwick{
    vector<ll>v,fw;
    void build(){
        fw.resize(v.size()+1,0);
    }
    void upd(ll i){
        i = upper_bound(all(v),i)-v.begin();
        for(;i<sz(fw);i+=i&-i)fw[i]++;
    }
    int qr(ll 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];
ll 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,ll 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,ll 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);
}
map<pii,ll>mp;
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,mp[{b[i].f,b[i].s}]=a[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,mp[{b[j].f,b[j].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,1e16)-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++]);
      |           ~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:75:38: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   75 |         ans[qq[i].i] = qr(1,1,n,id,n,1e16)-qr(1,1,n,id,n,qq[i].z-1);
      |                                      ^~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20944 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 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 12 ms 21852 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21944 KB Output is correct
10 Incorrect 10 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 491 ms 54872 KB Output is correct
2 Correct 490 ms 54828 KB Output is correct
3 Correct 497 ms 55148 KB Output is correct
4 Correct 279 ms 54408 KB Output is correct
5 Correct 440 ms 54748 KB Output is correct
6 Correct 169 ms 48464 KB Output is correct
7 Correct 478 ms 54876 KB Output is correct
8 Correct 476 ms 54952 KB Output is correct
9 Correct 455 ms 54856 KB Output is correct
10 Correct 313 ms 52288 KB Output is correct
11 Correct 183 ms 52240 KB Output is correct
12 Correct 115 ms 48308 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 54872 KB Output is correct
2 Correct 490 ms 54828 KB Output is correct
3 Correct 497 ms 55148 KB Output is correct
4 Correct 279 ms 54408 KB Output is correct
5 Correct 440 ms 54748 KB Output is correct
6 Correct 169 ms 48464 KB Output is correct
7 Correct 478 ms 54876 KB Output is correct
8 Correct 476 ms 54952 KB Output is correct
9 Correct 455 ms 54856 KB Output is correct
10 Correct 313 ms 52288 KB Output is correct
11 Correct 183 ms 52240 KB Output is correct
12 Correct 115 ms 48308 KB Output is correct
13 Incorrect 522 ms 54872 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20828 KB Output is correct
2 Correct 4 ms 20944 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 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 12 ms 21852 KB Output is correct
8 Correct 12 ms 21852 KB Output is correct
9 Correct 12 ms 21944 KB Output is correct
10 Incorrect 10 ms 21852 KB Output isn't correct
11 Halted 0 ms 0 KB -