Submission #835091

#	Time	Username	Problem	Language	Result	Execution time	Memory
835091		sunwukong123	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	333 ms	118220 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 = 400005;
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=min(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=max(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;
map<int,int>mapper;
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;
int query(int L, int R){
	int res=0;
	for(int k=19;k>=0;k--){
		if(rtwok[L][k] != -1 && rtwok[L][k]<=R){
			res+=1<<k;
			L=rtwok[L][k];
		}
	}
	return res;
}
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	int m=2*n+2;
	memset(rtwok,-1,sizeof rtwok);
	mnseg=new node1(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]);
	}
	for(int i=0;i<=m;i++){
		rtwok[i][0]=mnseg->query(i,m);
		if(rtwok[i][0]==inf)rtwok[i][0]=-1;
	}
	for(int i=m;i>=0;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];
		}
	}
	vector<int>out;
	int sum = query(1,m);
	set<pi> s;
	s.insert({0,0});
	s.insert({m,m});
	for(int i=1;i<=n;i++){
		int L=A[i][0], R=A[i][1];

		if(fw.range_sum(L,R-1)>0){
			continue;
		}
		auto iter=s.lower_bound({L,-inf});
		int lf=prev(iter)->second;
		int rg=iter->first;
		if(sum+query(lf,L)+query(R,rg)-query(lf,rg)+1>=k && (int)out.size()<k){

			out.push_back(i);
			fw.update(A[i][0],A[i][1]-1,1);
			sum+=query(lf,L)+query(R,rg)-query(lf,rg)+1;
			s.insert({L,R});
		}
		
	}
	if(out.empty())cout<<-1<<'\n';
	else{

		assert((int)out.size()==k);
		for(auto x:out)cout<<x<<"\n";
	}
}

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