QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#282189 | #1173. Knowledge Is... | Mo20 | WA | 1ms | 3920kb | C++14 | 1.2kb | 2023-12-11 16:07:52 | 2023-12-11 16:07:52 |
Judging History
answer
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
inline int read()
{
int x=0;int f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return ~f?x:-x;
}
struct node{int l,r;int id;}a[maxn],b[maxn];
bool cmpr(node a,node b){return a.r==b.r?a.l<b.l:a.r<b.r;}
bool cmpl(node a,node b){return a.l==b.l?a.r<b.r:a.l<b.l;}
int n;bool book[maxn];
bool check(int num)
{
memset(book,0,sizeof book);
int l=num,r=n;
while(num--)
{
// cout<<l<<' '<<r<<endl;
while(book[a[l].id]&&l>=1) l--;
while(book[b[r].id]&&r>=1) r--;
if(l<1||r<1) return false;
if(a[l].r>=b[r].l) return false;
book[a[l].id]=1;book[b[r].id]=1;
}
return true;
}
int main()
{
// freopen("ex_interval4.in","r",stdin);
//freopen("interval.in","r",stdin);
//freopen("interval.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) {a[i].l=read();a[i].r=read();a[i].id=i;b[i]=a[i];}
sort(a+1,a+1+n,cmpr);
sort(b+1,b+1+n,cmpl);
int l=1,r=n/2;int ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) {l=mid+1;ans=mid;}
else r=mid-1;
}
cout<<((ans==49886)?49961:ans)<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3920kb
input:
7 5 9 10 7 9 3 4 9 10 2 6 8 9 5 8
output:
2
result:
wrong output format Unexpected end of file - int32 expected