QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33630#1429. HitxzzduangWA 4ms7848kbC++2.3kb2022-06-04 14:23:512022-06-04 14:23:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-04 14:23:52]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:7848kb
  • [2022-06-04 14:23:51]
  • 提交

answer

#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<set>
#define fi first
#define se second
#define N 100005
using namespace std;
inline int read(){
	int x=0,f=0; char ch=getchar();
	while(!isdigit(ch)) f|=(ch==45),ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
int n,cnt,p[N],ans,lsh[2*N],m,mnr[2*N],vld[2*N],nxt[2*N][18],mnl[2*N],mx;
pair<int,int> a[N];
set<int> s;
multiset<int> ss;
int main(){
	for(int cas=read();cas--;){
		n=read();
		ss.clear();
		for(int i=1;i<=n;++i) a[i].fi=read(),a[i].se=read(),ss.insert(a[i].se);
		sort(a+1,a+n+1);
		cnt=0;
		int pos=0;
		while(pos<n){
			auto it=ss.begin();
			p[++cnt]=*it;
			while(pos+1<=n && a[pos+1].fi<=p[cnt]){
				++pos;
				auto fick=ss.lower_bound(a[pos].se);
				ss.erase(fick);
			}
		}
		ans=0;
		for(int i=1;i<=n;++i){
			int l=lower_bound(p+1,p+cnt+1,a[i].fi)-p;
			int r=upper_bound(p+1,p+cnt+1,a[i].se)-p-1;
			ans=max(ans,r-l+1);
		}
		ans--;
		m=0;
		for(int i=1;i<=n;++i) lsh[++m]=a[i].fi,lsh[++m]=a[i].se;
		sort(lsh+1,lsh+m+1);
		m=unique(lsh+1,lsh+m+1)-lsh-1;
		for(int i=1;i<=m+1;++i) mnr[i]=mnl[i]=1e9+10;
		mx=0;
		for(int i=1;i<=n;++i){
			int l=lower_bound(lsh+1,lsh+m+1,a[i].fi)-lsh;
			int r=lower_bound(lsh+1,lsh+m+1,a[i].se)-lsh;
			mnr[l]=min(mnr[l],r);
			mnl[r]=min(mnl[r],l);
			mx=max(mx,l);
		}
		for(int i=m;i>=1;--i){
			mnr[i-1]=min(mnr[i-1],mnr[i]);
			mnl[i-1]=min(mnl[i-1],mnl[i]);
		}
		for(int i=1;i<=m;++i){
			vld[i]=0;
			for(int j=0;j<=17;++j) nxt[i][j]=0;
		}
		s.clear();
		for(int i=m;i>=1;--i){
			if(i>=mx){
				vld[i]=1;
				s.insert(i);
				continue;
			}
			auto it=s.upper_bound(mnr[i+1]);
			if(it==s.begin()){
				vld[i]=0;
				continue;
			}
			it--;
			nxt[i][0]=*it;
			for(int j=1;j<=17;++j) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
			int now=i;
			for(int j=0;j<=17;++j) if(ans&(1<<j)) now=nxt[now][j];
			if(!now || mnl[now]>i) vld[i]=1;
			if(vld[i]) s.insert(i);
		}
		int ok=0;
		for(int i=1;i<=mnr[1];++i)
			if(vld[i]){ok=i;break;}
		if(ok){
			printf("%d ",ans);
			cnt=0;
			while(ok){
				p[++cnt]=lsh[ok];
				ok=nxt[ok][0];
			}
		}
		else printf("%d ",ans+1);
		printf("%d ",cnt);
		for(int i=1;i<=cnt;++i) printf("%d ",p[i]);
		puts("");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 7816kb

input:

4
4
0 1
2 3
4 5
3 5
5
0 70
0 10
20 30
40 50
60 70
8
-1 7
-2 -1
-9 -7
-8 9
-9 -7
-2 4
-7 4
3 9
5
0 1
0 2
2 3
3 5
4 5

output:

1 3 0 2 5 
4 4 10 30 50 70 
2 3 -9 -1 9 
2 3 1 3 5 

result:

ok ok, tt = 4

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 7848kb

input:

1
1
0 1

output:

0 1 0 

result:

wrong answer test 1: invalid result: 0