제출 #887003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887003		imarn	Examination (JOI19_examination)	C++14	20 / 100	626 ms	72592 KiB

examination

#include "bits/stdc++.h"
#define f first
#define s second
#define ll long long
#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();
        //cout<<i<<"\n";
        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 b[N];
ll c[N];
void build(int i,int l,int r){
    if(l==r){
        t[i].v.pb(b[l].s+b[l].f);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){
        t[i].upd(v);return;
    }
    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,pii>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].s>>b[i].f,c[i]=b[i].f,mp[{b[i].s,b[i].f}].s=b[i].f+b[i].s;
    sort(b+1,b+1+n);sort(c+1,c+n+1);build(1,1,n);
    for(int i=n;i>=1;i--)mp[{b[i].s,b[i].f}].f=i,swap(b[i].f,b[i].s);sort(b+1,b+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=n;
    for(int i=0;i<q;i++){
        while(j>0&&b[j].f>=qq[i].x){
            int id=upper_bound(c+1,c+n+1,b[j].s-1)-c;
            upd(1,1,n,id,mp[{b[j].f,b[j].s}].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";
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
      |           ~~^~~~~~~~~~~~~~~~
examination.cpp:40:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
      |                               ~~^~~~~~~~~~~~~~~~~~
examination.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     }while(li<t[2*i].v.size())t[i].v.pb(t[2*i].v[li++]);
      |            ~~^~~~~~~~~~~~~~~~
examination.cpp:44:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     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:69:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   69 |     for(int i=n;i>=1;i--)mp[{b[i].s,b[i].f}].f=i,swap(b[i].f,b[i].s);sort(b+1,b+n+1);
      |     ^~~
examination.cpp:69:70: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |     for(int i=n;i>=1;i--)mp[{b[i].s,b[i].f}].f=i,swap(b[i].f,b[i].s);sort(b+1,b+n+1);
      |                                                                      ^~~~

• Subtask 1: 0 / 2
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57