Submission #34620056

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const long long N=2e6+5,INF=1e18;
long long n,ans;
long long a[N],b[N];
long long v[N],vid;


long long f[N*4],g[N*4];
multiset <long long> S[N*4];


void build(long long l,long long r,long long o){
	if(l==r){
		f[o]=INF;
		g[o]=l;
		return ;
	}
	long long mid=(l+r)>>1;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
	if(f[o<<1]<=f[o<<1|1]) f[o]=f[o<<1],g[o]=g[o<<1];
	else f[o]=f[o<<1|1],g[o]=g[o<<1|1];
}
void modify(long long l,long long r,long long o,long long x,long long k){
	if(l==r){
		f[o]=min(f[o],k);
		S[o].insert(k);
		return ;
	}
	long long mid=(l+r)>>1;
	if(x<=mid) modify(l,mid,o<<1,x,k);
	else modify(mid+1,r,o<<1|1,x,k);
	if(f[o<<1]<=f[o<<1|1]) f[o]=f[o<<1],g[o]=g[o<<1];
	else f[o]=f[o<<1|1],g[o]=g[o<<1|1];
}
void del(long long l,long long r,long long o,long long x,long long k){
	if(l==r){
		S[o].erase(S[o].find(k));
		if(!S[o].size()) f[o]=INF;
		else f[o]=*(--S[o].end());
		return ;
	}
	long long mid=(l+r)>>1;
	if(x<=mid) del(l,mid,o<<1,x,k);
	else del(mid+1,r,o<<1|1,x,k);
	if(f[o<<1]<=f[o<<1|1]) f[o]=f[o<<1],g[o]=g[o<<1];
	else f[o]=f[o<<1|1],g[o]=g[o<<1|1];
}

long long mn,mner;
void query(long long l,long long r,long long o,long long L,long long R){
	if(L<=l && r<=R){
		if(f[o]<mn) mn=f[o],mner=g[o];
		return ;
	}
	long long mid=(l+r)>>1;
	if(L<=mid) query(l,mid,o<<1,L,R);
	if(R>mid) query(mid+1,r,o<<1|1,L,R);
}

priority_queue <long long> Q;

long long c[N];
long long lowbit(long long x){
	return x & (-x);
}
void modi(long long x,long long k){
	while(x<=vid) c[x]+=k,x+=lowbit(x);
}
long long que(long long x){
	long long tot=0;
	while(x) tot+=c[x],x-=lowbit(x);
	return tot;
}

multiset <long long> T;

int main(){
	cin>>n;
	for(long long i=1;i<=n;i++) cin>>a[i]>>b[i],v[++vid]=a[i],v[++vid]=b[i];
	sort(v+1,v+vid+1);
	vid=unique(v+1,v+vid+1)-v-1;
	
	build(1,vid,1);
	
	for(long long i=1;i<=n;i++){
		a[i]=lower_bound(v+1,v+vid+1,a[i])-v;
		b[i]=lower_bound(v+1,v+vid+1,b[i])-v;
		
		if(a[i]>=b[i]) modify(1,vid,1,a[i],b[i]),ans++;
		else Q.push(b[i]),modi(a[i],1),T.insert(a[i]);
	}
	
	while(Q.size()){
		long long u=Q.top(); Q.pop();
		
		long long x=que(vid)-que(u-1);
		if(x){
			long long p=*(--T.end());
			T.erase(T.find(p));
			modi(p,-1);
		}
		else{
			mn=INF;
			query(1,vid,1,u,vid);
			if(mn==INF) return puts("-1"),0;
			del(1,vid,1,mner,mn);
			ans--;
			
			Q.push(mn);
		}
	}
	cout<<ans;
}

Submission Info

Submission Time
Task E - Examination
User PineAppleBlue17
Language C++ (GCC 9.2.1)
Score 0
Code Size 2504 Byte
Status WA
Exec Time 941 ms
Memory 440332 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 4
AC × 66
WA × 20
Set Name Test Cases
Sample sample_00.txt, sample_01.txt, sample_02.txt, sample_03.txt
All case_00.txt, case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, case_22.txt, case_23.txt, case_24.txt, case_25.txt, case_26.txt, case_27.txt, case_28.txt, case_29.txt, case_30.txt, case_31.txt, case_32.txt, case_33.txt, case_34.txt, case_35.txt, case_36.txt, case_37.txt, case_38.txt, case_39.txt, case_40.txt, case_41.txt, case_42.txt, case_43.txt, case_44.txt, case_45.txt, case_46.txt, case_47.txt, case_48.txt, case_49.txt, case_50.txt, case_51.txt, case_52.txt, case_53.txt, case_54.txt, case_55.txt, case_56.txt, case_57.txt, case_58.txt, case_59.txt, case_60.txt, case_61.txt, case_62.txt, case_63.txt, case_64.txt, case_65.txt, case_66.txt, case_67.txt, case_68.txt, case_69.txt, case_70.txt, case_71.txt, case_72.txt, case_73.txt, case_74.txt, case_75.txt, case_76.txt, case_77.txt, case_78.txt, case_79.txt, case_80.txt, case_81.txt, sample_00.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
case_00.txt AC 276 ms 378468 KiB
case_01.txt AC 255 ms 378504 KiB
case_02.txt AC 254 ms 378420 KiB
case_03.txt AC 251 ms 378400 KiB
case_04.txt AC 252 ms 378536 KiB
case_05.txt AC 254 ms 378532 KiB
case_06.txt AC 538 ms 411596 KiB
case_07.txt AC 406 ms 396444 KiB
case_08.txt AC 465 ms 408188 KiB
case_09.txt AC 716 ms 437872 KiB
case_10.txt AC 260 ms 379096 KiB
case_11.txt AC 778 ms 440244 KiB
case_12.txt AC 784 ms 440168 KiB
case_13.txt AC 783 ms 440188 KiB
case_14.txt AC 786 ms 440196 KiB
case_15.txt AC 781 ms 440180 KiB
case_16.txt AC 591 ms 411092 KiB
case_17.txt AC 576 ms 410520 KiB
case_18.txt AC 528 ms 408496 KiB
case_19.txt AC 265 ms 379668 KiB
case_20.txt AC 444 ms 396424 KiB
case_21.txt AC 617 ms 412052 KiB
case_22.txt AC 266 ms 380368 KiB
case_23.txt AC 767 ms 418120 KiB
case_24.txt AC 829 ms 436024 KiB
case_25.txt AC 749 ms 417208 KiB
case_26.txt AC 920 ms 440160 KiB
case_27.txt AC 910 ms 440260 KiB
case_28.txt AC 908 ms 440204 KiB
case_29.txt AC 922 ms 440244 KiB
case_30.txt AC 939 ms 440168 KiB
case_31.txt AC 921 ms 440216 KiB
case_32.txt AC 935 ms 440140 KiB
case_33.txt AC 932 ms 440276 KiB
case_34.txt AC 932 ms 440240 KiB
case_35.txt AC 934 ms 440272 KiB
case_36.txt AC 941 ms 440216 KiB
case_37.txt AC 927 ms 440192 KiB
case_38.txt AC 928 ms 440192 KiB
case_39.txt AC 926 ms 440172 KiB
case_40.txt AC 908 ms 440192 KiB
case_41.txt AC 926 ms 440264 KiB
case_42.txt AC 922 ms 440272 KiB
case_43.txt AC 912 ms 440236 KiB
case_44.txt AC 912 ms 440180 KiB
case_45.txt AC 909 ms 440268 KiB
case_46.txt AC 539 ms 434572 KiB
case_47.txt AC 540 ms 434688 KiB
case_48.txt AC 541 ms 434712 KiB
case_49.txt AC 538 ms 434696 KiB
case_50.txt WA 394 ms 394868 KiB
case_51.txt WA 404 ms 395788 KiB
case_52.txt WA 401 ms 395756 KiB
case_53.txt WA 380 ms 392840 KiB
case_54.txt WA 360 ms 390552 KiB
case_55.txt WA 426 ms 396640 KiB
case_56.txt WA 287 ms 382520 KiB
case_57.txt WA 315 ms 385552 KiB
case_58.txt WA 423 ms 397052 KiB
case_59.txt WA 442 ms 398840 KiB
case_60.txt WA 476 ms 403132 KiB
case_61.txt WA 475 ms 403044 KiB
case_62.txt WA 476 ms 403236 KiB
case_63.txt WA 470 ms 403096 KiB
case_64.txt WA 472 ms 403232 KiB
case_65.txt WA 474 ms 403124 KiB
case_66.txt WA 471 ms 403180 KiB
case_67.txt WA 472 ms 403092 KiB
case_68.txt WA 475 ms 403028 KiB
case_69.txt WA 473 ms 403160 KiB
case_70.txt AC 257 ms 378360 KiB
case_71.txt AC 255 ms 378504 KiB
case_72.txt AC 257 ms 378484 KiB
case_73.txt AC 258 ms 378368 KiB
case_74.txt AC 335 ms 387860 KiB
case_75.txt AC 693 ms 419648 KiB
case_76.txt AC 347 ms 393072 KiB
case_77.txt AC 471 ms 408148 KiB
case_78.txt AC 800 ms 440332 KiB
case_79.txt AC 791 ms 440228 KiB
case_80.txt AC 797 ms 440128 KiB
case_81.txt AC 805 ms 440200 KiB
sample_00.txt AC 256 ms 378480 KiB
sample_01.txt AC 254 ms 378432 KiB
sample_02.txt AC 256 ms 378508 KiB
sample_03.txt AC 254 ms 378508 KiB