Submission #441890

#	Time	Username	Problem	Language	Result	Execution time	Memory
441890		kig9981	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	418 ms	76192 KiB

event2

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct Seg
{
	int l, r, v;
	Seg() : l(0), r(0), v(0) {}
} tree[5555555];

const int SZ=1<<18;
vector<int> x(1);
vector<pair<int,int>> S;
int node_cnt, tor[2*SZ], lazy[2*SZ], L[2*SZ], R[2*SZ];

void set_tree(int b, int n, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree[p].v=1;
		return;
	}
	if(n<=m) {
		if(tree[p].l==tree[b].l) tree[tree[p].l=node_cnt++]=tree[tree[b].l];
		set_tree(tree[b].l,n,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==tree[b].r) tree[tree[p].r=node_cnt++]=tree[tree[b].r];
		set_tree(tree[b].r,n,tree[p].r,m+1,e);
	}
	tree[p].v=tree[tree[p].l].v+tree[tree[p].r].v;
}

int get_r(int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(tree[p].v==0) return -1;
	if(s==e) return m;
	if(tree[tree[p].r].v) return get_r(tree[p].r,m+1,e);
	return get_r(tree[p].l,s,m);
}

int get_sum(int n1, int n2, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(n2<n1 || n2<s || e<n1 || p==0) return 0;
	if(n1<=s && e<=n2) return tree[p].v;
	return get_sum(n1,n2,tree[p].l,s,m)+get_sum(n1,n2,tree[p].r,m+1,e);
}

void lazy_propagation(int bit, int s, int e)
{
	if(lazy[bit]) {
		tor[bit]=1;
		if(s<e) lazy[2*bit]=lazy[2*bit+1]=1;
		lazy[bit]=0;
	}
}

void or_tree(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return;
	if(n1<=s && e<=n2) {
		lazy[bit]=1;
		lazy_propagation(bit,s,e);
		return;
	}
	or_tree(n1,n2,2*bit,s,m);
	or_tree(n1,n2,2*bit+1,m+1,e);
	tor[bit]=tor[2*bit]|tor[2*bit+1];
}

int get_or(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1) return 0;
	if(n1<=s && e<=n2) return tor[bit];
	return get_or(n1,n2,2*bit,s,m)|get_or(n1,n2,2*bit+1,m+1,e);
}

int get_lp(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1, t;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1 || !tor[bit]) return SZ;
	if(s==e) return m;
	if((t=get_lp(n1,n2,2*bit,s,m))<SZ) return t;
	return get_lp(n1,n2,2*bit+1,m+1,e);
}

int get_rp(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1, t;
	lazy_propagation(bit,s,e);
	if(n2<n1 || n2<s || e<n1 || !tor[bit]) return -1;
	if(s==e) return m;
	if((t=get_rp(n1,n2,2*bit+1,m+1,e))>-1) return t;
	return get_rp(n1,n2,2*bit,s,m);
}

int get_lv(int n)
{
	int ret=L[n+=SZ];
	while(n>>=1) ret+=L[n];
	return ret;
}

int get_rv(int n)
{
	int ret=R[n+=SZ];
	while(n>>=1) ret+=R[n];
	return ret;
}

void add_lv(int s, int e, int v)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) L[s++]+=v;
		if(~e&1) L[e--]+=v;
	}
}

void add_rv(int s, int e, int v)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) R[s++]+=v;
		if(~e&1) R[e--]+=v;
	}
}

void set_lv(int n, int v) {L[n+SZ]+=v-get_lv(n);}
void set_rv(int n, int v) {R[n+SZ]+=v-get_rv(n);}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, K, cnt=0;
	cin>>N>>K; S.resize(N);
	for(auto &[l,r]: S) {
		cin>>l>>r;
		x.push_back(l);
		x.push_back(r);
	}
	sort(x.begin(),x.end()); x.resize(node_cnt=unique(x.begin(),x.end())-x.begin());
	memset(R,-1,sizeof(R));
	for(int i=0;i<N;i++) {
		auto &[l,r]=S[i];
		l=lower_bound(x.begin(),x.end(),l)-x.begin();
		r=lower_bound(x.begin(),x.end(),r)-x.begin();
		R[r]=max(R[r],l);
	}
	for(int i=1;i<x.size();i++) {
		tree[i]=tree[i-1];
		if(R[i]>-1 && get_r(i-1)<R[i]) {
			tree[i]=tree[R[i]];
			set_tree(R[i],R[i],i);
		}
	}
	if(tree[x.size()-1].v<K) {
		cout<<"-1\n";
		return 0;
	}
	memset(R,0,sizeof(R));
	or_tree(0,0); or_tree(x.size()-1,x.size()-1);
	for(int i=0;i<N;i++) {
		auto[l,r]=S[i];
		if(get_or(l,r-1)) continue;
		int s=get_rp(0,l)+1, e=get_lp(r,SZ-1), sv=get_lv(s), ev=get_rv(e), lv=get_sum(s,l,l), rv=get_sum(r,e,e), tv=get_sum(s,e,e);
		if(sv+lv+1+rv+ev<K || ++cnt>K) continue;
		or_tree(l,r-1);
		add_rv(0,s,lv+rv+1-tv); set_rv(l,ev+rv+1);
		add_lv(e,SZ-1,lv+rv+1-tv); set_lv(r,sv+lv+1);
		cout<<i+1<<'\n';
	}
	return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:167:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |  for(int i=1;i<x.size();i++) {
      |              ~^~~~~~~~~

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