제출 #405575

#제출 시각아이디문제언어결과실행 시간메모리
405575dvdg6566Event Hopping 2 (JOI21_event2)C++14
32 / 100
3075 ms19928 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pi; typedef vector<ll> vi; typedef vector<pi> vpi; #define pb emplace_back #define f first #define s second #define mp make_pair #define SZ(x) (ll)x.size() #define ALL(x) x.begin(),x.end() #define lb lower_bound #define ub upper_bound const int MAXN = 200100; const int MAXK = 19; int L[MAXN][MAXK]; vpi V; vi des; int N,a,b,M,K; int eval(int x,int y){ int ans=0; // for(int k=MAXK-1;k>=0;--k)if(x<=y){ // if(L[x][k]-1<=y){ // x = L[x][k] + 1; // ans += (1<<k); // } // } while(x<=y&&L[x][0]-1<=y){ // fits within (x,y) x = L[x][0]; ++ans; } return ans; } set<pair<pi,int>> S; int main(){ cin>>N>>K; for(int i=0;i<N;++i){ cin>>a>>b; --b; V.pb(a,b); des.pb(a);des.pb(b); } sort(ALL(des));des.resize(unique(ALL(des))-des.begin()); for(auto &i:V){ i.f = lb(ALL(des),i.f) - des.begin(); i.s = lb(ALL(des),i.s) - des.begin(); } vpi T; for(auto i:V)T.pb(i); sort(ALL(T)); M=SZ(des)-1; // run from 0 to M-1 ll rc=1e9; for(int i=M;i>=0;--i){ while(SZ(T)&&T.back().f>=i){ rc=min(rc,T.back().s); T.pop_back(); } L[i][0]=rc+1; for(int k=1;k<MAXK;++k){ if(L[i][k-1] >= 1e9)continue; int t=L[i][k-1]; ++t; L[i][k] = L[t][k-1]; } } int tot=eval(0,M); // cerr<<tot<<'\n'; if(tot<K){ cout<<-1<<'\n'; return 0; } S.insert(mp(mp(-1,-1),-1)); S.insert(mp(mp(0,M),tot)); vi ans; for(int i=0;i<N;++i){ a = V[i].f; b = V[i].s; auto x = --S.ub(mp(mp(a,1e9),-1e9)); pi rng=x->f; int w=x->s; if(rng.f>a)assert(0); if(rng.s<b)continue; // rng.f, a, b, rng.s int c=eval(rng.f,a-1); int d=eval(b+1,rng.s); int nv=c+d; if(tot-w+1+nv<K)continue; // cannot take tot = tot-w+1+nv; ans.pb(i+1); S.erase(x); if(c)S.insert(mp(mp(rng.f,a-1),c)); if(d)S.insert(mp(mp(b+1,rng.s),d)); // cerr<<"Ins "<<i+1<<'\n'; } while(SZ(ans)>K)ans.pop_back(); for(auto i:ans)cout<<i<<'\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...