QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607920#1173. Knowledge Is...Hollow_knight_WA 0ms11972kbC++141.2kb2024-10-03 17:05:062024-10-03 17:05:07

Judging History

你现在查看的是最新测评结果

  • [2024-10-03 17:05:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11972kb
  • [2024-10-03 17:05:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+15;
inline ll read(){
	ll x=0;char f=1,c=getchar();
	while(c<48||c>57){if(c=='-')f=0;c=getchar();}
	while(c>=48&&c<=57){x=(x<<1)+(x<<3)+ll(c)-48;c=getchar();}
	return f==1?x:-x;
}
int n,p[N],l[N],r[N],vl[N],vr[N];
inline bool cmpl(int x,int y){return l[x]>l[y];}
inline bool cmpr(int x,int y){return r[x]<r[y];}
inline bool check(int x){
	for(int i=1,j=x;i<=x;++i,--j){
		if(r[vr[i]]>=l[vl[j]])return false;
	}
	return true;
}
int solve(){
	n=read();
	for(int i=1;i<=n;++i){
		l[i]=read(),r[i]=read();
	}
	for(int i=1;i<=n;++i)p[i]=i;
	sort(p+1,p+n+1,cmpr);
	for(int i=1;i<=n;++i)vr[i]=p[i];
	sort(p+1,p+n+1,cmpl);
	for(int i=1;i<=n;++i)vl[i]=p[i];
	int l=0,r=n/2,mid=0,ans=0;
	while(l<=r){
		mid=((l+r)>>1);
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}
/*
5
9 13
3 7
9 12
7 10
3 7
2

10
37 41
78 84
30 37
94 98
52 58
3 9
76 83
58 62
50 56
17 25
5
*/
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=1;
	while(T--){
		solve();
	}
	fclose(stdin),fclose(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 11972kb

input:

7 5
9 10
7 9
3 4
9 10
2 6
8 9
5 8

output:

3

result:

wrong output format Unexpected end of file - int32 expected