제출 #445095

#제출 시각아이디문제언어결과실행 시간메모리
445095mosiashvililukaEvent Hopping 2 (JOI21_event2)C++14
0 / 100
94 ms19568 KiB
#include<bits/stdc++.h> #define mk make_pair using namespace std; const int N=1000000002; int a,b,c,d,e,i,j,ii,jj,zx,xc,k,sf[100009],mshrg[100009][19],pr[100009],mshlf[100009][19],lef,rig,mid,pas; pair <int, int> p[100009]; pair <pair <int, int>, int> P[100009]; pair <pair <int, int>, pair <int, int> > PP; set <pair <pair <int, int>, pair <int, int> > > s; set <pair <pair <int, int>, pair <int, int> > >::iterator it,tt; set <int> S; set <int>::iterator IT; int left(int q, int w){ int sm=0; for(int h=17; h>=0; h--){ if(mshlf[q][h]<=0||mshlf[q][h]>=a+1) continue; if(p[mshlf[q][h]].first<w) continue; sm+=(1<<h); q=mshlf[q][h]; } return sm; } int right(int q, int w){ int sm=0; for(int h=17; h>=0; h--){ if(mshrg[q][h]<=0||mshrg[q][h]>=a+1) continue; if(p[mshrg[q][h]].second>w) continue; sm+=(1<<h); q=mshrg[q][h]; } return sm; } int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>a>>k; for(i=1; i<=a; i++){ cin>>p[i].first>>p[i].second; P[i].first=p[i];P[i].second=i; } sort(P+1,P+a+1); sf[a]=a; for(i=a-1; i>=1; i--){ if(P[i].first.second<=P[sf[i+1]].first.second){ sf[i]=i; }else{ sf[i]=sf[i+1]; } } for(i=1; i<=a; i++){ lef=0;rig=a+1; while(1){ if(lef+1>=rig) break; mid=(lef+rig)/2; if(P[mid].first.first<p[i].second){ lef=mid; }else{ rig=mid; } } mshrg[i][0]=P[lef+1].second; //cout<<i<<" "<<mshrg[i][0]<<endl; } for(i=1; i<=a; i++){ P[i].first.first=p[i].second;P[i].first.second=p[i].first; P[i].second=i; } sort(P+1,P+a+1); for(i=1; i<=a; i++) swap(P[i].first.first,P[i].first.second); pr[1]=1; for(i=2; i<=a; i++){ if(P[i].first.first>=P[pr[i-1]].first.first){ pr[i]=i; }else{ pr[i]=pr[i-1]; } } for(i=1; i<=a; i++){ lef=0;rig=a+1; while(1){ if(lef+1>=rig) break; mid=(lef+rig)/2; if(P[mid].first.second>p[i].first){ rig=mid; }else{ lef=mid; } } mshlf[i][0]=P[rig-1].second; //cout<<i<<" "<<mshlf[i][0]<<endl; } for(j=1; j<=17; j++){ for(i=1; i<=a; i++){ mshlf[i][j]=mshlf[mshlf[i][j-1]][j-1]; mshrg[i][j]=mshrg[mshrg[i][j-1]][j-1]; } } //cout<<right(3,100)<<endl; //cout<<left(3,3)<<endl; //return 0; //s.insert(make_pair(make_pair(0,0),make_pair())) pas=0; s.insert(mk(mk(0,0),mk(0,0))); s.insert(mk(mk(N,N),mk(0,0))); for(i=1; i<=a; i++){ if(s.size()>=k+2) break; it=s.lower_bound(mk(mk(p[i].first,0),mk(0,0))); if((*it).first.first<p[i].second) continue; it--; if((*it).first.second>p[i].first) continue; it++; e=pas; pas-=(*it).second.first; //cout<<i<<" "<<pas<<endl; it--; c=left(i,(*it).first.second); it++; pas+=c; d=right(i,(*it).first.first); pas+=d; pas++; //cout<<i<<" "<<pas<<endl; if(pas<k){ pas=e; continue; } PP=(*it); s.erase(it); s.insert(mk(PP.first,mk(d,PP.second.second))); s.insert(mk(mk(p[i].first,p[i].second),mk(c,i))); } if(/*pas<k*/s.size()<k+2){ cout<<-1; return 0; } for(it=s.begin(); it!=s.end(); it++){ if((*it).second.second==0) continue; S.insert((*it).second.second); } for(IT=S.begin(); IT!=S.end(); IT++){ cout<<(*IT)<<"\n"; k--; if(k==0) break; } return 0; }

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

event2.cpp: In function 'int main()':
event2.cpp:111:14: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |   if(s.size()>=k+2) break;
      |      ~~~~~~~~^~~~~
event2.cpp:139:22: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |  if(/*pas<k*/s.size()<k+2){
      |              ~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...