QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33630 | #1429. Hit | xzzduang | WA | 4ms | 7848kb | C++ | 2.3kb | 2022-06-04 14:23:51 | 2022-06-04 14:23:52 |
Judging History
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