제출 #341006

#제출 시각아이디문제언어결과실행 시간메모리
341006ogibogi2004Examination (JOI19_examination)C++14
0 / 100
1998 ms66128 KiB
//八(^□^*) #include<bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=3e5+6; const ll SQRT=600; ll n,q; ll ans[MAXN]; set<pair<ll,ll> >xs; set<ll>ys,zs; ll s[MAXN],t[MAXN],sum[MAXN]; ll x[MAXN],y[MAXN],z[MAXN]; map<pair<ll,ll>,ll>newx; map<ll,ll>newy,newz; struct student { ll a,b,c; student(){} student(ll _a,ll _b,ll _c) { a=_a;b=_b;c=_c; } bool operator<(student const& other)const { return b<other.b; } }; struct query { ll a,b,c,pos; query(){} query(ll _a,ll _b,ll _c,ll _pos) { a=_a;b=_b;c=_c;pos=_pos; } bool operator<(query const& other)const { return b<other.b; } }; vector<student>blocks1[SQRT]; vector<query>blocks2[SQRT]; ll BIT[MAXN]; void update(ll idx,ll val) { ++idx; for(;idx<MAXN;idx+=idx&(-idx)) { BIT[idx]+=val; } } ll query(ll idx) { ++idx; ll ret=0; for(;idx>0;idx-=idx&(-idx)) { ret+=BIT[idx]; } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>q; for(ll i=1;i<=n;++i) { cin>>s[i]>>t[i]; xs.insert({s[i],i}); sum[i]=s[i]+t[i]; ys.insert(t[i]);zs.insert(sum[i]); } ll cntx=0,cnty=0,cntz=0; for(auto xd:xs) { newx[xd]=++cntx; } for(auto xd:ys) { newy[xd]=++cnty; } for(auto xd:zs) { newz[xd]=++cntz; } for(ll i=1;i<=q;++i) { cin>>x[i]>>y[i]>>z[i]; xs.insert({x[i],-i}); auto it=ys.lower_bound(y[i]); if(it==ys.end())y[i]=cnty+1; else y[i]=newy[(*it)]; it=zs.lower_bound(z[i]); if(it==zs.end())z[i]=cntz+1; else z[i]=newz[(*it)]; } for(auto xd:xs) { newx[xd]=++cntx; } for(ll i=1;i<=n;++i) { s[i]=newx[{s[i],i}]; t[i]=newy[t[i]]; sum[i]=newz[sum[i]]; } for(ll i=1;i<=q;i++) { x[i]=newx[{x[i],-i}]; } //cout<<"students:\n"; for(ll i=1;i<=n;++i) { //cout<<s[i]<<" "<<t[i]<<" "<<sum[i]<<endl; blocks1[s[i]/SQRT].push_back({s[i],t[i],sum[i]}); } //cout<<"criterias:\n"; for(ll i=1;i<=q;++i) { //cout<<x[i]<<" "<<y[i]<<" "<<z[i]<<endl; blocks2[x[i]/SQRT].push_back({x[i],y[i],z[i],i}); } vector<student>computed,eh,oh; for(ll j=SQRT-1;j>=0;--j) { if(blocks1[j].size()==0&&blocks2[j].size()==0)continue; memset(BIT,0,sizeof(BIT)); /*cout<<"block1 "<<j<<":\n"; for(ll i=0;i<blocks1[j].size();++i) { cout<<blocks1[j][i].a<<" "<<blocks1[j][i].b<<" "<<blocks1[j][i].c<<"\n"; } cout<<endl; cout<<"block2 "<<j<<":\n"; for(ll i=0;i<blocks2[j].size();++i) { cout<<blocks2[j][i].a<<" "<<blocks2[j][i].b<<" "<<blocks2[j][i].c<<" "<<blocks2[j][i].pos<<"\n"; } cout<<endl;*/ for(ll i1=0;i1<blocks2[j].size();++i1) { for(ll i2=0;i2<blocks1[j].size();++i2) { if(blocks2[j][i1].a<=blocks1[j][i2].a&&blocks2[j][i1].b<=blocks1[j][i2].b&&blocks2[j][i1].c<=blocks1[j][i2].c) { ans[blocks2[j][i1].pos]++; } } } sort(blocks2[j].rbegin(),blocks2[j].rend()); ll p=computed.size()-1; for(ll i=0;i<blocks2[j].size();++i) { while(p>0&&computed[p].b>=blocks2[j][i].b) { update(computed[p].c,+1); p--; } ans[blocks2[j][i].pos]+=(computed.size()-p-1)-query(blocks2[j][i].c-1); } eh.clear(); for(ll i=0;i<blocks1[j].size();++i) { eh.push_back(blocks1[j][i]); } sort(eh.begin(),eh.end()); oh.clear(); ll i1=0,i2=0; while(i1<eh.size()||i2<computed.size()) { if(i1==eh.size()) { oh.push_back(computed[i2]); ++i2; } else if(i2==computed.size()) { oh.push_back(eh[i1]); ++i1; } else if(eh[i1]<computed[i2]) { oh.push_back(eh[i1]); ++i1; } else { oh.push_back(computed[i2]); ++i2; } } computed=oh; /*cout<<"computed:\n"; for(ll j=0;j<computed.size();j++) { cout<<computed[j].a<<" "<<computed[j].b<<" "<<computed[j].c<<endl; }*/ } for(ll i=1;i<=q;++i) { cout<<ans[i]<<"\n"; } return 0; }

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

examination.cpp: In function 'int main()':
examination.cpp:142:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for(ll i1=0;i1<blocks2[j].size();++i1)
      |               ~~^~~~~~~~~~~~~~~~~~
examination.cpp:144:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |    for(ll i2=0;i2<blocks1[j].size();++i2)
      |                ~~^~~~~~~~~~~~~~~~~~
examination.cpp:154:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for(ll i=0;i<blocks2[j].size();++i)
      |              ~^~~~~~~~~~~~~~~~~~
examination.cpp:164:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   for(ll i=0;i<blocks1[j].size();++i)
      |              ~^~~~~~~~~~~~~~~~~~
examination.cpp:171:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   while(i1<eh.size()||i2<computed.size())
      |         ~~^~~~~~~~~~
examination.cpp:171:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   while(i1<eh.size()||i2<computed.size())
      |                       ~~^~~~~~~~~~~~~~~~
examination.cpp:173:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |    if(i1==eh.size())
      |       ~~^~~~~~~~~~~
examination.cpp:178:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<student>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |    else if(i2==computed.size())
      |            ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...