Submission #71514957

Source Code Expand

#include<bits/stdc++.h>
const int M = 4e5 + 10;
using namespace std;
struct Que{
	int L,R;
}Q[M];
int B[M<<1],sz;
struct Segment{
	struct node{
		int L,R,cnt,val;
		int Lazy;
	}tree[M<<2];
	void Up(int p){
		tree[p].val=tree[p<<1].val+tree[p<<1|1].val;
	}
	void Down(int p){
		if(tree[p].Lazy){
			tree[p<<1].Lazy=true;tree[p<<1|1].Lazy=true;
			tree[p<<1].val=tree[p<<1].cnt;
			tree[p<<1|1].val=tree[p<<1|1].cnt;
			tree[p].Lazy=false;
		}
	}
	void Build(int L,int R,int p){
		tree[p].L=L;tree[p].R=R;tree[p].val=0;
		tree[p].cnt=B[R+1]-B[L];
		tree[p].Lazy=0;
		if(L==R)return;
		int mid=(L+R)>>1;
		Build(L,mid,p<<1);
		Build(mid+1,R,p<<1|1);
		Up(p);
	}
	void Update(int Lx,int Rx,int p){
		if(Lx<=tree[p].L&&tree[p].R<=Rx){
			tree[p].Lazy=true;
			tree[p].val=tree[p].cnt;
			return;
		}
		int mid=(tree[p].L+tree[p].R)>>1;
		Down(p);
		if(Rx<=mid)Update(Lx,Rx,p<<1);
		else if(Lx>mid)Update(Lx,Rx,p<<1|1);
		else {Update(Lx,mid,p<<1);Update(mid+1,Rx,p<<1|1);}
		Up(p);
	}
}ST;
int Get_id(int x){
	return lower_bound(B+1,B+sz+1,x)-B;
}
int main(){
	int n , q;
	cin >> n >> q;
	B[++sz]=n+1;
	for(int i=1;i<=q;i++){
		scanf("%d%d",&Q[i].L,&Q[i].R);
		B[++sz]=Q[i].L;
		B[++sz]=Q[i].R+1;
	}
	sort(B+1,B+sz+1);
	sz=unique(B+1,B+sz+1)-B-1;
	ST.Build(1,sz,1);
	for(int i=1;i<=q;i++){
		int L=Get_id(Q[i].L),R=Get_id(Q[i].R+1)-1;
		ST.Update(L,R,1);
		printf("%d\n",n-ST.tree[1].val);
	}
	return 0;
}

Submission Info

Submission Time
Task E - Cover query
User Hacker_
Language C++23 (GCC 15.2.0)
Score 450
Code Size 1468 Byte
Status AC
Exec Time 225 ms
Memory 27556 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 2
AC × 42
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt
Case Name Status Exec Time Memory
example_00.txt AC 1 ms 3616 KiB
example_01.txt AC 1 ms 3860 KiB
hand_00.txt AC 76 ms 27476 KiB
hand_01.txt AC 68 ms 17148 KiB
hand_02.txt AC 78 ms 27448 KiB
hand_03.txt AC 99 ms 27448 KiB
hand_04.txt AC 77 ms 27296 KiB
hand_05.txt AC 97 ms 27476 KiB
hand_06.txt AC 94 ms 27556 KiB
hand_07.txt AC 32 ms 7076 KiB
hand_08.txt AC 29 ms 6996 KiB
hand_09.txt AC 36 ms 6996 KiB
hand_10.txt AC 27 ms 6912 KiB
hand_11.txt AC 27 ms 6916 KiB
random_00.txt AC 224 ms 27388 KiB
random_01.txt AC 224 ms 27452 KiB
random_02.txt AC 224 ms 27352 KiB
random_03.txt AC 224 ms 27556 KiB
random_04.txt AC 225 ms 27460 KiB
random_05.txt AC 169 ms 27464 KiB
random_06.txt AC 168 ms 27484 KiB
random_07.txt AC 168 ms 27440 KiB
random_08.txt AC 168 ms 27352 KiB
random_09.txt AC 168 ms 27400 KiB
random_10.txt AC 104 ms 6908 KiB
random_11.txt AC 104 ms 7076 KiB
random_12.txt AC 104 ms 6936 KiB
random_13.txt AC 104 ms 7064 KiB
random_14.txt AC 105 ms 7064 KiB
random_15.txt AC 87 ms 6960 KiB
random_16.txt AC 86 ms 6908 KiB
random_17.txt AC 86 ms 6996 KiB
random_18.txt AC 87 ms 6916 KiB
random_19.txt AC 86 ms 6972 KiB
random_20.txt AC 172 ms 27440 KiB
random_21.txt AC 171 ms 27452 KiB
random_22.txt AC 171 ms 27460 KiB
random_23.txt AC 171 ms 27476 KiB
random_24.txt AC 171 ms 27296 KiB
random_25.txt AC 189 ms 27448 KiB
random_26.txt AC 189 ms 27428 KiB
random_27.txt AC 190 ms 27440 KiB