oj.uz

답안 #886983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886983 2023-12-13T11:31:09 Z imarn Examination (JOI19_examination) C++14
20 / 100
 520 ms 48904 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);
}
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,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:74:38: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   74 |         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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 4 ms 20828 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 11 ms 21592 KB Output is correct
8 Correct 12 ms 21548 KB Output is correct
9 Correct 13 ms 21596 KB Output is correct
10 Incorrect 9 ms 21592 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 48480 KB Output is correct
2 Correct 469 ms 48588 KB Output is correct
3 Correct 487 ms 48720 KB Output is correct
4 Correct 195 ms 48464 KB Output is correct
5 Correct 415 ms 48716 KB Output is correct
6 Correct 184 ms 48460 KB Output is correct
7 Correct 455 ms 48904 KB Output is correct
8 Correct 440 ms 48460 KB Output is correct
9 Correct 467 ms 48716 KB Output is correct
10 Correct 279 ms 48332 KB Output is correct
11 Correct 158 ms 48228 KB Output is correct
12 Correct 117 ms 48200 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 48480 KB Output is correct
2 Correct 469 ms 48588 KB Output is correct
3 Correct 487 ms 48720 KB Output is correct
4 Correct 195 ms 48464 KB Output is correct
5 Correct 415 ms 48716 KB Output is correct
6 Correct 184 ms 48460 KB Output is correct
7 Correct 455 ms 48904 KB Output is correct
8 Correct 440 ms 48460 KB Output is correct
9 Correct 467 ms 48716 KB Output is correct
10 Correct 279 ms 48332 KB Output is correct
11 Correct 158 ms 48228 KB Output is correct
12 Correct 117 ms 48200 KB Output is correct
13 Incorrect 520 ms 48460 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 4 ms 20828 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 11 ms 21592 KB Output is correct
8 Correct 12 ms 21548 KB Output is correct
9 Correct 13 ms 21596 KB Output is correct
10 Incorrect 9 ms 21592 KB Output isn't correct
11 Halted 0 ms 0 KB -