oj.uz

Submission #417215

# Submission time Handle Problem Language Result Execution time Memory
417215 2021-06-03T13:19:12 Z errorgorn Event Hopping 2 (JOI21_event2) C++17
0 / 100
 815 ms 27396 KB 
#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+1;
			int r=(*next(iter)).fi;
			
			int val=curr-calc(l,r)+calc(l,arr[x].fi)+calc(arr[x].se+1,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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17484 KB Output is correct
2 Correct 14 ms 17560 KB Output is correct
3 Correct 14 ms 17484 KB Output is correct
4 Incorrect 815 ms 27396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17484 KB Output is correct
2 Correct 16 ms 17532 KB Output is correct
3 Correct 13 ms 17484 KB Output is correct
4 Correct 13 ms 17504 KB Output is correct
5 Correct 13 ms 17444 KB Output is correct
6 Correct 14 ms 17464 KB Output is correct
7 Correct 16 ms 17560 KB Output is correct
8 Correct 14 ms 17532 KB Output is correct
9 Correct 14 ms 17484 KB Output is correct
10 Correct 13 ms 17484 KB Output is correct
11 Correct 14 ms 17528 KB Output is correct
12 Correct 13 ms 17464 KB Output is correct
13 Correct 13 ms 17484 KB Output is correct
14 Correct 14 ms 17540 KB Output is correct
15 Correct 14 ms 17456 KB Output is correct
16 Incorrect 14 ms 17488 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17484 KB Output is correct
2 Correct 16 ms 17532 KB Output is correct
3 Correct 13 ms 17484 KB Output is correct
4 Correct 13 ms 17504 KB Output is correct
5 Correct 13 ms 17444 KB Output is correct
6 Correct 14 ms 17464 KB Output is correct
7 Correct 16 ms 17560 KB Output is correct
8 Correct 14 ms 17532 KB Output is correct
9 Correct 14 ms 17484 KB Output is correct
10 Correct 13 ms 17484 KB Output is correct
11 Correct 14 ms 17528 KB Output is correct
12 Correct 13 ms 17464 KB Output is correct
13 Correct 13 ms 17484 KB Output is correct
14 Correct 14 ms 17540 KB Output is correct
15 Correct 14 ms 17456 KB Output is correct
16 Incorrect 14 ms 17488 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17484 KB Output is correct
2 Correct 14 ms 17560 KB Output is correct
3 Correct 14 ms 17484 KB Output is correct
4 Incorrect 815 ms 27396 KB Output isn't correct
5 Halted 0 ms 0 KB -