Submission #386403

#	Time	Username	Problem	Language	Result	Execution time	Memory
386403		haojiandan	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	558 ms	39660 KiB

event2

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int INF=(1e9)+10;
const int maxn=(1e5)+10;
int n,m;
struct node { int l,r; } d[maxn],e[maxn];
bool cmpr(node A,node B) {
	if (A.r==B.r) return A.l>B.l;
	return A.r<B.r;
}
int nxt[maxn],fa[maxn][20],Lmx[maxn][20],lg[maxn];
int now,old;
set<int> s1,s2;
set<int>::iterator it;
int queryLmx(int l,int r) {
	int j=lg[r-l+1];
	return max(Lmx[l][j],Lmx[r-(1<<j)+1][j]);
}
int ans[maxn],top,TMP[maxn];
int query(int L,int R) {
	int ed=upper_bound(TMP+1,TMP+n+1,R)-TMP-1;
	int l=1,r=ed,mid,res=0;
	while (l<=r) {
		mid=(l+r)>>1;
		if (queryLmx(1,mid)>=L) res=mid,r=mid-1;
		else l=mid+1;
	}
	if (res==0) return 0;
	int x=res,cnt=1;
	for (int i=19;i>=0;i--) {
	//	printf("x=%d,i=%d,fa=%d\n",x,i,fa[x][i]);
		if (fa[x][i]<=ed) cnt+=(1<<i),x=fa[x][i];
	}
	return cnt;
	
}
int lsh[maxn*2],N;
namespace BIT {
	ll tr[maxn*8];
	int lazy[maxn*8],sz[maxn*8];
	void build(int l,int r,int root) {
		sz[root]=r-l+1;
		if (l==r) return;
		int mid=(l+r)>>1; build(l,mid,root<<1),build(mid+1,r,root<<1|1);
	}
	void puttag(int root,int delta) {
		tr[root]+=(ll)delta*sz[root]; lazy[root]+=delta;
	}
	void pushdown(int root) {
		if (lazy[root]) puttag(root<<1,lazy[root]),puttag(root<<1|1,lazy[root]),lazy[root]=0;
	}
	void add(int L,int R,int l,int r,int root) {
		if (L<=l&&r<=R) { puttag(root,1); return; }
		int mid=(l+r)>>1; pushdown(root);
		if (L<=mid) add(L,R,l,mid,root<<1);
		if (mid<R) add(L,R,mid+1,r,root<<1|1);
		tr[root]=tr[root<<1]+tr[root<<1|1];
	}
	ll query(int L,int R,int l,int r,int root) {
		if (L<=l&&r<=R) return tr[root];
		int mid=(l+r)>>1; pushdown(root); ll sum=0;
		if (L<=mid) sum=query(L,R,l,mid,root<<1);
		if (mid<R) sum+=query(L,R,mid+1,r,root<<1|1);
		return sum;
	}
};
int main() {
	//freopen("4.in","r",stdin);
	read(n),read(m);
	for (int i=1;i<=n;i++) {
		read(d[i].l),read(d[i].r),e[i]=d[i];
		lsh[++N]=d[i].l,lsh[++N]=d[i].r-1;
	}
	sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1;
	sort(d+1,d+n+1,cmpr);
	nxt[n]=nxt[n+1]=n+1;
	for (int i=1;i<=n;i++) Lmx[i][0]=d[i].l;
	for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for (int i=1;i<=19;i++) for (int j=1;j+(1<<i)-1<=n;j++)
		Lmx[j][i]=max(Lmx[j][i-1],Lmx[j+(1<<i-1)][i-1]);
	int l,r,res,mid,x,y;
	for (int i=1;i<=n;i++) TMP[i]=d[i].r;
	for (int i=n-1;i>=1;i--) {
		res=n+1,l=i+1,r=n;
		while (l<=r) {
			mid=(l+r)>>1;
			if (queryLmx(i+1,mid)>=d[i].r) res=mid,r=mid-1;
			else l=mid+1;
		}
		nxt[i]=res;
	}
	BIT::build(1,N,1);
	/*for (int i=1;i<=n;i++) {
		printf("[%d,%d],%d\n",d[i].l,d[i].r,nxt[i]);
	}*/
	for (int i=1;i<=n+1;i++) fa[i][0]=nxt[i];
	for (int i=1;i<=19;i++) for (int j=1;j<=n+1;j++) fa[j][i]=fa[fa[j][i-1]][i-1];
	now=query(0,INF);
	//printf("%d\n",now);
	//exit(0);
	if (now<m) { puts("-1"); return 0; }
	// s1 : l
	// s2 : r
	s1.insert(INF),s2.insert(0);
	int A,B;
	for (int i=1;i<=n;i++) {
		A=lower_bound(lsh+1,lsh+N+1,e[i].l)-lsh,B=lower_bound(lsh+1,lsh+N+1,e[i].r-1)-lsh;
		//printf("[%d,%d]\n",A,B);
		it=s2.upper_bound(e[i].l); it--;
		x=(*it);
		it=s1.lower_bound(e[i].r);
		y=(*it);
		if (x>y||BIT::query(A,B,1,N,1)) continue;
		old=now;
		now-=query(x,y);
		now+=query(x,e[i].l)+query(e[i].r,y)+1;
		//printf("? i=%d , %d %d %d %d, %d\n",i,x,e[i].l,e[i].r,y,now);
		if (now>=m) {
			ans[++top]=i,s1.insert(e[i].l),s2.insert(e[i].r);
			BIT::add(A,B,1,N,1);
		}
		else now=old;
		if (top>=m) break;
	}
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:86:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   86 |   Lmx[j][i]=max(Lmx[j][i-1],Lmx[j+(1<<i-1)][i-1]);
      |                                       ~^~

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