제출 #895447

#제출 시각아이디문제언어결과실행 시간메모리
8954478pete8Event Hopping 2 (JOI21_event2)C++17
0 / 100
3021 ms38184 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<float.h> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") using namespace std; #define int long long #define double long double const int mod=998244353,mxn=2e5+5,lg=22,inf=1e18,minf=-1e18,Mxn=100000; int n,k,sz; struct info{int l,r,posl,posr,realid,id;}; bool cmp(info a,info b){ if(a.r==b.r)return a.l>b.l; return a.r<b.r; } vector<info>v; vector<int>compress; int up[mxn+10][lg+5]; int jump(int at,int bound){ int cnt=0; for(int i=lg;i>=0;i--)if(up[at][i]!=-1&&v[up[at][i]].posr<=bound)at=up[at][i],cnt+=(1ll<<i); return cnt; } int32_t main(){ fastio cin>>n>>k; for(int i=0;i<n;i++){ int a,b;cin>>a>>b; v.pb({a,b,-1,-1,i,i}); compress.pb(a); compress.pb(b); } sort(all(compress)); unique(all(compress)); for(auto &i:v){ i.posl=lb(all(compress),i.l)-compress.begin(); i.posr=lb(all(compress),i.r)-compress.begin(); } int cur=0; vector<info>v2(all(v)); sort(all(v),cmp); for(int i=0;i<n;i++)v2[v[i].realid].id=i; int curcnt=0,at=0; for(int j=0;j<=lg;j++)for(int i=0;i<n;i++)up[i][j]=-1; for(int i=0;i<n;i++)while(cur<n&&v[cur].r<=v[i].l){ up[cur][0]=i; cur++; } for(int j=1;j<=lg;j++)for(int i=0;i<n;i++)if(up[i][j-1]!=-1)up[i][j]=up[up[i][j-1]][j-1]; curcnt=jump(0,inf); vector<int>ans; set<int>st; int add=0; for(int i=0;i<n;i++){ int upb=inf,l,r; auto it=st.lb(v2[i].id); if(it==st.begin())l=0; else{ it--; l=(*it); it++; } if(it!=st.begin()&&v[l].r>v2[i].l)continue; if(it!=st.end())r=(*it); else r=n-1; if(it!=st.end()&&v2[i].r>v[r].l)continue; int mx=v[l].r;//brute force at=l; while(at<v.size()&&v[at].r<=v2[i].l){ if(v[at].l>=mx)mx=v[at].r,add++; at++; } at=v2[i].id; mx=v[i].r; while(at<v.size()&&v[at].r<=v[r].l){ if(v[at].l>=mx)mx=v[at].r,add++; at++; } at=l; while(at<v.size()&&v[at].r<=v[r].l){ if(v[at].l>=mx)mx=v[at].r,add--; at++; } //add=jump(l,v2[i].l)+jump(v2[i].id,v[r].l)-jump(l,v[r].l); if(curcnt+add+1<k)continue; curcnt+=add+1; ans.pb(i+1); st.insert(v2[i].id); if(ans.size()==k)break; } if(ans.size()<k)cout<<-1<<'\n'; else for(int i=0;i<k;i++)cout<<ans[i]<<"\n"; return 0; }

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

event2.cpp: In function 'int32_t main()':
event2.cpp:97:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   while(at<v.size()&&v[at].r<=v2[i].l){
      |         ~~^~~~~~~~~
event2.cpp:103:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   while(at<v.size()&&v[at].r<=v[r].l){
      |         ~~^~~~~~~~~
event2.cpp:108:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   while(at<v.size()&&v[at].r<=v[r].l){
      |         ~~^~~~~~~~~
event2.cpp:117:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  117 |   if(ans.size()==k)break;
      |      ~~~~~~~~~~^~~
event2.cpp:83:7: warning: unused variable 'upb' [-Wunused-variable]
   83 |   int upb=inf,l,r;
      |       ^~~
event2.cpp:119:15: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  119 |  if(ans.size()<k)cout<<-1<<'\n';
      |     ~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...