QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#607920 | #1173. Knowledge Is... | Hollow_knight_ | WA | 0ms | 11972kb | C++14 | 1.2kb | 2024-10-03 17:05:06 | 2024-10-03 17:05:07 |
Judging History
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