QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607881#1173. Knowledge Is...Sai_tqwqWA 2ms7768kbC++141.7kb2024-10-03 16:51:042024-10-03 16:51:05

Judging History

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

  • [2024-10-03 16:51:05]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7768kb
  • [2024-10-03 16:51:04]
  • 提交

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