Submission #834952

#	Time	Username	Problem	Language	Result	Execution time	Memory
834952		sunwukong123	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	299 ms	147112 KiB

event2

#include <bits/stdc++.h>
using namespace std;
#define int long long 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 200005;
const int inf=1000000500ll;
const int oo =1000000000000000000ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n,k;
array<int,3> A[MAXN];
int rtwok[MAXN][20];
int ltwok[MAXN][20];
struct node1 {
	int s,e,m,val;
	node1 *l, *r;
	node1 (int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		val=inf;
		if(s!=e){
			l=new node1(s,m);
			r=new node1(m+1,e);
		}
	}
	void update(int x, int nval){
		if(s==e){
			val=nval;
			return;
		}
		if(x>m)r->update(x,nval);
		else l->update(x,nval);
		val=min(l->val,r->val);
	}
	int query(int x, int y){
		if(s==x&&e==y){
			return val;
		}
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return min(l->query(x,m), r->query(m+1,y));
	}
}*mnseg;
struct node2{
	int s,e,m,val;
	node2 *l, *r;
	node2 (int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		val=-1;
		if(s!=e){
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	void update(int x, int nval){
		if(s==e){
			val=nval;
			return;
		}
		if(x>m)r->update(x,nval);
		else l->update(x,nval);
		val=max(l->val,r->val);
	}
	int query(int x, int y){
		if(s==x&&e==y){
			return val;
		}
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return max(l->query(x,m), r->query(m+1,y));
	}
}*mxseg;
map<int,int> to_n;
map<int,int> to_1;
struct fenw {
	int fw[MAXN], fw2[MAXN];
	void update(int x, int y, int v) { //inclusive
	    for (int tx=x; tx < MAXN; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
	    for (int ty=y+1; ty < MAXN; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
	}
	int sum (int x) {
	    int res = 0;
	    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
	    return res;    
	}
	int range_sum(int x, int y) { //inclusive
	    return sum(y)-sum(x-1);
	}
}fw;
map<int,int> mapper;
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	int m=2*n;
	memset(rtwok,-1,sizeof rtwok);
	memset(ltwok,-1,sizeof ltwok);
	mnseg=new node1(0,m);
	mxseg=new node2(0,m);

	vector<pair<int,int>> in;
	vector<int> disc;
	for(int i=1;i<=n;i++){
		int a,b; cin >> a >> b;
		in.push_back({a,b});
		disc.push_back(a);
		disc.push_back(b);
	}
	sort(disc.begin(),disc.end());
	disc.resize(unique(disc.begin(),disc.end())-disc.begin());
	for(int i=0;i<(int)disc.size();i++){
		mapper[disc[i]]=i+1;
	}

	for(int i=1;i<=n;i++){
		A[i][0] = mapper[in[i-1].first];
		A[i][1] = mapper[in[i-1].second];
		A[i][2] = i;
	}
	for(int i=1;i<=n;i++){
		mnseg->update(A[i][0],A[i][1]);
		mxseg->update(A[i][1],A[i][0]);
	}
	for(int i=1;i<=m;i++){
		rtwok[i][0]=mnseg->query(i,m);
		if(rtwok[i][0]==inf)rtwok[i][0]=-1;
		ltwok[i][0]=mxseg->query(1,i);

	}
	for(int i=m;i>=1;i--){
		for(int j=1;j<=19;j++){
			if(rtwok[i][j-1] == -1)continue;
			rtwok[i][j]=rtwok[rtwok[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=19;++j){
			if(ltwok[i][j-1]==-1)continue;
			ltwok[i][j]=ltwok[ltwok[i][j-1]][j-1];
		}
	}
	vector<int>out;
	for(int i=1;i<=n;i++){
		int L=A[i][0], R=A[i][1];
		if(fw.range_sum(L+1,R-1)){
			continue;
		}
		auto it=to_n.lower_bound(R);
		pair<int,int> gn={m+1,0};
		if(it!=to_n.end())gn=*it;
		int sum = 1;
		int sumL = 0, sumR=0;
		for(int k=19;k>=0;k--){
			if(rtwok[R][k] != -1 && rtwok[R][k] <= gn.first){
				R=rtwok[R][k];
				sum+=(1<<k);
				sumR+=(1<<k);
			}
		}
		sumR+=gn.second;
		sum+=gn.second;

		it=to_1.upper_bound(L);
		pair<int,int> g1={0,0};
		if(it!=to_1.begin())g1=*prev(it);
		for(int k=19;k>=0;k--){
			if(ltwok[L][k] != -1 && ltwok[L][k] >= g1.first){
				L=ltwok[L][k];
				sum+=(1<<k);
				sumL+=(1<<k);
			}
		}
		sumL+=g1.second;
		sum+=g1.second;
		if(sum>=k && (int)out.size()<k){
			out.push_back(i);
			fw.update(A[i][0],A[i][1],1);
			to_n[A[i][0]]=1+sumR;
			to_1[A[i][1]]=1+sumL;
		} 
	}
	if(out.empty())cout<<-1;
	else{
		for(auto x:out)cout<<x<<"\n";
	}
}

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