Submission #417217

#	Time	Username	Problem	Language	Result	Execution time	Memory
417217		errorgorn	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	1196 ms	28760 KiB

event2

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	int val=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int k){
		if (s==e) val=k;
		else{
			if (i<=m) l->update(i,k);
			else r->update(i,k);
			
			val=max(l->val,r->val);
		}
	}
	
	int query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,100005);

int n,k;
ii arr[100005];

ii sorted[100005];
int nxt[100005][20];


set<ii> s;
// we need to check if the intercept of all ranges is null
// find the range exactly after the tile
// then check the range exactly before it?

bool in(ii i){
	auto it=s.ub(ii(i.se,-1));
	
	if (it==s.begin()) return false;
	
	return (*prev(it)).se>i.fi;
}

//we just need some way to find the max number of things we can take
//when we only allow taking stuff from a certain range

int calc(int l,int r){
	int lo=-1,hi=n+1,mi;
	
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (root->query(0,mi)>=l) hi=mi;
		else lo=mi;
	}
	
	int curr=hi;
	if (sorted[curr].se>r) return 0;
	
	int ans=1;
	rep(x,20,0){
		int temp=nxt[curr][x];
		if (temp==-1) continue;
		if (sorted[temp].se<=r) curr=temp,ans+=(1<<x);
	}
	
	return ans;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
	rep(x,0,n) sorted[x]=arr[x];
	
	sort(sorted,sorted+n,[](ii i,ii j){
		return i.se<j.se;
	});
	sorted[n]=ii(1e9+100,1e9+100);
	
	//rep(x,0,n) cout<<sorted[x].fi<<" "<<sorted[x].se<<endl;
	rep(x,0,n) root->update(x,sorted[x].fi);
	root->update(n,1e9+100);
	
	memset(nxt,-1,sizeof(nxt));
	rep(x,0,n){
		int lo=x,hi=n+1,mi;
		while (hi-lo>1){
			mi=hi+lo>>1;
			
			if (root->query(x+1,mi)>=sorted[x].se) hi=mi;
			else lo=mi;
		}
		
		nxt[x][0]=hi;
	}
	
	rep(x,n,0){
		int curr=nxt[x][0];
		rep(y,0,20){
			if (curr==-1) break;
			curr=nxt[x][y+1]=nxt[curr][y];
		}
	}
	
	//rep(x,0,n) cout<<nxt[x][0]<<" "; cout<<endl;
	
	int curr=calc(0,1e9);
	if (curr<k){
		cout<<"-1"<<endl;
		return 0;
	}
	
	vector<int> ans;
	
	s.insert(ii(0,0));
	s.insert(ii(1e9+1,1e9+1));
	
	rep(x,0,n){
		if (!in(arr[x])){
			auto iter=s.insert(arr[x]).fi;
			int l=(*prev(iter)).se;
			int r=(*next(iter)).fi;
			
			int val=curr-calc(l,r)+calc(l,arr[x].fi)+calc(arr[x].se,r)+1;
			
			//cout<<val<<endl;
			//cout<<l<<" "<<arr[x].fi<<" "<<arr[x].se+1<<" "<<r<<endl;
			
			if (val>=k){
				ans.pub(x);
				curr=val;
			}
			else{
				s.erase(arr[x]);
			}
		}
		
		//for (auto &it:s) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
		//cout<<endl;
	}
	
	rep(x,0,k) cout<<ans[x]+1<<endl;
}

Compilation message (stderr)

event2.cpp: In constructor 'node::node(int, int)':
event2.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
event2.cpp: In function 'int calc(int, int)':
event2.cpp:82:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   mi=hi+lo>>1;
      |      ~~^~~
event2.cpp: In function 'int main()':
event2.cpp:123:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |    mi=hi+lo>>1;
      |       ~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61