제출 #121946

#제출 시각아이디문제언어결과실행 시간메모리
121946MvCExamination (JOI19_examination)C++11
2 / 100
3044 ms381124 KiB
#pragma GCC target("avx2") #pragma GCC optimization("O3") #pragma GCC optimization("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include<bits/stdc++.h> //#include "rail.h" #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=6e5+50; const int mod=1e9+7; using namespace std; using namespace __gnu_pbds; typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> order_set; int n,q,i,j,k,a[nmax],b[nmax],c[nmax],x[nmax],y[nmax],rs[nmax],nr,sm[nmax],s; order_set st[4*nmax]; vector<int>qr[nmax]; vector<pair<int,pair<int,int> > >qrr[nmax],vc; pair<int,pair<int,int> >p; void upd(int x,int l,int r,int p,int v) { st[x].in(mkp(v,nr)); if(l==r)return; int mid=(l+r)/2; if(p<=mid)upd(2*x,l,mid,p,v); else upd(2*x+1,mid+1,r,p,v); } int qry(int x,int l,int r,int tl,int tr,int v) { if(l>tr || r<tl)return 0; if(l>=tl && r<=tr) { v--; auto it=st[x].upper_bound(mkp(v,1e6)); if(it==st[x].end())return 0; pair<int,int> y=*it; int z=(int)st[x].size()-st[x].order_of_key(y); return z; } int mid=(l+r)/2; return qry(2*x,l,mid,tl,tr,v)+qry(2*x+1,mid+1,r,tl,tr,v); } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>q; for(i=1;i<=n;i++) { cin>>x[i]>>y[i]; vc.pb(mkp(x[i],mkp(0,i))); vc.pb(mkp(y[i],mkp(1,i))); vc.pb(mkp(x[i]+y[i],mkp(2,i))); } for(i=1;i<=q;i++) { cin>>a[i]>>b[i]>>c[i]; vc.pb(mkp(a[i],mkp(3,i))); vc.pb(mkp(b[i],mkp(4,i))); vc.pb(mkp(c[i],mkp(5,i))); } sort(vc.begin(),vc.end()); for(i=0;i<vc.size();) { k++; for(j=i;j<vc.size();j++) { if(vc[j].fr!=vc[i].fr)break; if(vc[j].sc.fr==2)sm[vc[j].sc.sc]=k; else if(vc[j].sc.fr==1)y[vc[j].sc.sc]=k; else if(vc[j].sc.fr==0)x[vc[j].sc.sc]=k; else if(vc[j].sc.fr==3)a[vc[j].sc.sc]=k; else if(vc[j].sc.fr==4)b[vc[j].sc.sc]=k; else if(vc[j].sc.fr==5)c[vc[j].sc.sc]=k; } i=j; } for(i=1;i<=n;i++) { qr[sm[i]].pb(i); //cout<<x[i]<<" "<<y[i]<<" "<<sm[i]<<endl; } for(i=1;i<=q;i++) { qrr[c[i]].pb(mkp(i,mkp(a[i],b[i]))); } for(i=k;i>=1;i--) { for(j=0;j<qr[i].size();j++) { s=qr[i][j]; nr++; upd(1,1,k,x[s],y[s]); } for(j=0;j<qrr[i].size();j++) { p=qrr[i][j]; rs[p.fr]=qry(1,1,k,p.sc.fr,k,p.sc.sc); } } for(i=1;i<=q;i++)cout<<rs[i]<<'\n'; return 0; }

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

examination.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
examination.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
examination.cpp: In function 'int main()':
examination.cpp:76:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vc.size();)
          ~^~~~~~~~~~
examination.cpp:79:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i;j<vc.size();j++)
           ~^~~~~~~~~~
examination.cpp:102:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qr[i].size();j++)
           ~^~~~~~~~~~~~~
examination.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qrr[i].size();j++)
           ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...