Submission #1044348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044348		pcc	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	137 ms	45052 KiB

event2

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


#define pii pair<int,int>
#define fs first
#define sc second
#define _all(T) T.begin(),T.end()
#define tiii tuple<int,int,int>

const int B = 20;
const int mxn = 2e5+10;
const int inf = 1e9+10;

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	pii seg[mxn*4];
	SEG(){}
	void modify(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r){
			seg[now].sc = 1;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e);
		if(mid<e)modify(rs,mid+1,r,s,e);
		seg[now].fs = seg[ls].fs|seg[ls].sc|seg[rs].fs|seg[rs].sc;
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].fs|seg[now].sc;
		if(mid>=e)return getval(ls,l,mid,s,e)|seg[now].sc;
		else if(mid<s)return getval(rs,mid+1,r,s,e)|seg[now].sc;
		else return seg[now].sc|getval(ls,l,mid,s,e)|getval(rs,mid+1,r,s,e);
	}
#undef ls
#undef rs
#undef mid
};
SEG seg;

pii arr[mxn];
vector<int> all;
int N,K;
int ldp[mxn][B],rdp[mxn][B];
set<tiii> st;
int sum = 0;


int jump(int s,int e,int dir){//if dir = 0:jump [s,e) if dir = 1:jump [e,s)
	int re = 0;
	for(int i = B-1;i>=0;i--){
		if(!dir){
			if(ldp[s][i]<e){
				re += 1<<i;
				s = ldp[s][i];
			}
		}
		else{
			if(rdp[e][i]>s){
				re += 1<<i;
				e = rdp[e][i];
			}
		}
	}
	if(!dir&&ldp[s][0]<=e)re++;
	if(dir&&rdp[e][0]>=s)re++;
	return re;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<=N;i++){
		auto &[a,b] = arr[i];
		cin>>a>>b;
		all.push_back(a);all.push_back(b-1);
	}
	all.push_back(-1);
	all.push_back(inf);
	sort(_all(all));all.resize(unique(_all(all))-all.begin());
	for(int i = 0;i<all.size();i++){
		for(int j = 0;j<B;j++)ldp[i][j] = all.size(),rdp[i][j] = -1;
	}
	for(int i = 0;i<B;i++)ldp[all.size()][i] = all.size(),rdp[0][i] = -1;
	for(int i = 1;i<=N;i++){
		auto &[a,b] = arr[i];
		a = lower_bound(_all(all),a)-all.begin();
		b = lower_bound(_all(all),b-1)-all.begin();
		ldp[a][0] = min(ldp[a][0],b+1);
		rdp[b][0] = max(rdp[b][0],a-1);//[l,r)
	}
	for(int i = 1;i<=all.size();i++){
		rdp[i][0] = max(rdp[i][0],rdp[i-1][0]);
		for(int j = 1;j<B;j++){
			int pre = rdp[i][j-1];
			if(pre>=0)rdp[i][j] = rdp[pre][j-1];
			rdp[i][j] = max(rdp[i][j],rdp[i-1][j]);
		}
	}
	for(int i = all.size()-1;i>=0;i--){
		ldp[i][0] = min(ldp[i][0],ldp[i+1][0]);
		for(int j = 1;j<B;j++){
			int pre = ldp[i][j-1];
			if(pre < all.size())ldp[i][j] = ldp[pre][j-1];
			ldp[i][j] = min(ldp[i][j],ldp[i+1][j]);
		}
	}
	/*
	cerr<<all.size()<<":";for(auto &i:all)cerr<<i<<',';cerr<<endl;
	for(int i = 1;i<all.size();i++){
		for(int j = 0;j<B;j++)cerr<<ldp[i][j]<<' ';cerr<<endl;
	}
	*/
	st.insert(tiii(1,all.size()-2,jump(0,all.size()-1,0)));
	sum = get<2>(*st.rbegin());
	vector<int> ans;
	for(int i = 1;i<=N;i++){
		bool flag = false;
		auto [s,e] = arr[i];
		if(seg.getval(0,0,all.size(),s,e))continue;
		int tsum = sum;
		auto it = --st.upper_bound(tiii(s+1,-1,-1));
		auto [l,r,v] = *it;
		tsum -= v;
		int tl,tr;
		if(l != s)tsum += (tl = jump(l-1,s-1,1));
		if(r != e)tsum += (tr = jump(e+1,r+1,0));
		tsum++;
		if(tsum>=K){
			st.erase(it);
			if(l != s)st.insert(tiii(l,s-1,tl));
			if(r != e)st.insert(tiii(e+1,r,tr));
			ans.push_back(i);
			seg.modify(0,0,all.size(),s,e);
			sum = tsum;
		}
	}
	while(ans.size()>K)ans.pop_back();
	if(ans.size()<K)cout<<"-1\n";
	else for(auto &i:ans)cout<<i<<'\n';
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:82:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
event2.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 1;i<=all.size();i++){
      |                ~^~~~~~~~~~~~
event2.cpp:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    if(pre < all.size())ldp[i][j] = ldp[pre][j-1];
      |       ~~~~^~~~~~~~~~~~
event2.cpp:119:8: warning: unused variable 'flag' [-Wunused-variable]
  119 |   bool flag = false;
      |        ^~~~
event2.cpp:139:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |  while(ans.size()>K)ans.pop_back();
      |        ~~~~~~~~~~^~
event2.cpp:140:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |  if(ans.size()<K)cout<<"-1\n";
      |     ~~~~~~~~~~^~

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