제출 #219055

#제출 시각아이디문제언어결과실행 시간메모리
219055kshitij_sodaniExamination (JOI19_examination)C++17
100 / 100
957 ms128084 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef int64_t llo; #define mp make_pair #define pb push_back #define a first #define b second #define endl "\n" bool cmp(pair<pair<llo,llo>,pair<llo,llo>> ac,pair<pair<llo,llo>,pair<llo,llo>> cc){ return ac.b.a<cc.b.a; } bool cmp2(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cd){ return ac.a.a+ac.a.b<cd.a.a+cd.a.b; } bool cmp3(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cc){ return ac.a.a<cc.a.a; } vector<llo> tree[400001]; vector<pair<llo,llo>> ss[400001]; vector<llo> indd[400001]; pair<llo,llo> bb[100001]; void setIO(string name) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((name+".in").c_str(),"r",stdin); // freopen((name+".out").c_str(),"w",stdout); } void u(llo no,llo i,llo j){ while(i<tree[no].size()){ tree[no][i]+=j; i+=(i&-i); } } llo st(llo no,llo i){ llo tot=0; while(i>0){ tot+=tree[no][i]; i-=(i&-i); } return tot; } void build(llo no,llo l,llo r){ for(llo i=l;i<=r+2;i++){ tree[no].pb(0); indd[no].pb(0); } if(r>l){ llo mid=(l+r)/2; build(no*2+1,l,mid); build(no*2+2,mid+1,r); llo ind=0; llo ind2=0; llo ind3=0; while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){ if(ss[no*2+1][ind].a<ss[no*2+2][ind2].a){ ss[no].pb(ss[no*2+1][ind]); indd[no][ss[no*2+1][ind].b-l]=ind3; ind+=1; ind3+=1; } else{ ss[no].pb(ss[no*2+2][ind2]); indd[no][ss[no*2+2][ind2].b-l]=ind3; ind2+=1; ind3+=1; } } while(ind<ss[no*2+1].size() ){ ss[no].pb(ss[no*2+1][ind]); indd[no][ss[no*2+1][ind].b-l]=ind3; ind+=1; ind3+=1; } while(ind2<ss[no*2+2].size()){ ss[no].pb(ss[no*2+2][ind2]); indd[no][ss[no*2+2][ind2].b-l]=ind3; ind2+=1; ind3+=1; } } else{ ss[no].pb({bb[l].b,l}); } } void update(llo no,llo l,llo r,llo ind){ if(ind<l or ind>r){ return; } u(no,indd[no][ind-l]+1,1); if(r>l){ llo mid=(l+r)/2; update(no*2+1,l,mid,ind); update(no*2+2,mid+1,r,ind); } } llo kk; llo cp; llo query(llo no,llo l,llo r){ if(bb[r].a<kk){ return 0; } if(bb[l].a>=kk){ if(ss[no][r-l].a<cp){ return 0; } llo low=0; llo high=r-l; while(low<high-1){ llo mid=(low+high)/2; if(ss[no][mid].a>=cp){ high=mid; } else{ low=mid+1; } } llo dd=high; if(ss[no][low].a>=cp){ dd=low; } llo xx=st(no,r-l+1); if(dd>0){ xx-=st(no,dd); } return xx; } else{ llo mid=(l+r)/2; return query(no*2+1,l,mid)+query(no*2+2,mid+1,r); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); llo n,q; //setIO("11"); cin>>n>>q; vector<pair<pair<llo,llo>,llo>> aa; llo mm,nn; for(llo i=0;i<n;i++){ cin>>mm>>nn; aa.pb({{mm,nn},0}); } sort(aa.begin(),aa.end(),cmp3); for(llo i=0;i<n;i++){ aa[i].b=i; } for(llo i=0;i<n;i++){ bb[i]=aa[i].a; } sort(aa.begin(),aa.end(),cmp2); llo pp,bc,cd; vector<pair<pair<llo,llo>,pair<llo,llo>>> qq; for(llo i=0;i<q;i++){ cin>>pp>>bc>>cd; qq.pb({{pp,bc},{cd,i}}); } sort(qq.begin(),qq.end(),cmp); llo pos=n-1; llo ans[q]; build(0,0,n-1); // cout<<33<<endl; for(llo ii=q-1;ii>=0;ii--){ llo ba=qq[ii].b.a; while(pos>=0){ if(aa[pos].a.a+aa[pos].a.b>=ba){ update(0,0,n-1,aa[pos].b); // cout<<aa[pos].b<<" "<<ii<<endl; pos-=1; } else{ break; } } kk=qq[ii].a.a; cp=qq[ii].a.b; llo ans4=query(0,0,n-1); ans[qq[ii].b.b]=ans4; } for(llo i=0;i<q;i++){ cout<<ans[i]<<endl; } return 0; }

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

examination.cpp: In function 'void u(llo, llo, llo)':
examination.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<tree[no].size()){
        ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void build(llo, llo, llo)':
examination.cpp:54:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
         ~~~^~~~~~~~~~~~~~~~~~
examination.cpp:54:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
                                   ~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:68:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() ){
         ~~~^~~~~~~~~~~~~~~~~~
examination.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<ss[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'void setIO(std::__cxx11::string)':
examination.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((name+".in").c_str(),"r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...