oj.uz

Submission #405571

# Submission time Handle Problem Language Result Execution time Memory
405571 2021-05-16T14:38:45 Z dvdg6566 Event Hopping 2 (JOI21_event2) C++14
0 / 100
 182 ms 21784 KB 
#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]<=y){
			x = L[x][k] + 1;
			ans += (1<<k);
		}
	}
	// while(x<=y&&L[x]<=y){ // fits within (x,y)
	// 	x = L[x]+1;
	// 	++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';
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 182 ms 21784 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 182 ms 21784 KB Output isn't correct
5 Halted 0 ms 0 KB -