QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#607881 | #1173. Knowledge Is... | Sai_tqwq | WA | 2ms | 7768kb | C++14 | 1.7kb | 2024-10-03 16:51:04 | 2024-10-03 16:51:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
int n,b[1000009],ans;
struct Interval{int l,r;}a[500009];
multiset<pair<int,int> > s1,s2;
struct segtree{
int mn[1000009<<2],tg[1000009<<2];
void pushup(int p){mn[p]=min(mn[p<<1],mn[p<<1|1]);}
void pushdown(int p){
if(!tg[p])return ;
mn[p<<1]+=tg[p];tg[p<<1]+=tg[p];
mn[p<<1|1]+=tg[p];tg[p<<1|1]+=tg[p];
tg[p]=0;
}
void upd(int xl,int xr,int x,int l,int r,int p){
if(xl<=l&&r<=xr)return mn[p]+=x,tg[p]+=x,void();
int mid=l+r>>1;
pushdown(p);
if(xl<=mid)upd(xl,xr,x,l,mid,p<<1);
if(xr>mid)upd(xl,xr,x,mid+1,r,p<<1|1);
pushup(p);
}
}tr;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r,b[2*i-1]=a[i].l,b[2*i]=a[i].r;
sort(b+1,b+1+2*n);
for(int i=1;i<=n;i++){
a[i].l=lower_bound(b+1,b+1+2*n,a[i].l)-b;
a[i].r=lower_bound(b+1,b+1+2*n,a[i].r)-b;
tr.upd(1,a[i].l,1,1,2*n,1);
}
sort(a+1,a+1+n,[&](Interval x,Interval y){
return x.r<y.r;
});
for(int i=1;i<=n;i++){
tr.upd(1,a[i].l,-1,1,2*n,1);
tr.upd(1,a[i].r,-1,1,2*n,1);
s1.insert({a[i].l,a[i].r});
while(tr.mn[1]<0){
auto p=*s1.rbegin();
s1.erase(--s1.end());
tr.upd(1,p.first,1,1,2*n,1);
tr.upd(1,p.second,1,1,2*n,1);
s2.insert(p);
}
while(!s2.empty()){
auto p=*s2.begin();
tr.upd(1,p.first,-1,1,2*n,1);
tr.upd(1,p.second,-1,1,2*n,1);
if(tr.mn[1]<0){
tr.upd(1,p.first,1,1,2*n,1);
tr.upd(1,p.second,1,1,2*n,1);
break;
}
s2.erase(s2.begin());
s1.insert(p);
}
ans=max(ans,(int)s1.size());
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7768kb
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