QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111026 | #1429. Hit | Kostlin | WA | 3ms | 7652kb | C++14 | 3.0kb | 2023-06-05 15:27:32 | 2023-06-05 15:27:35 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define fi first
#define sc second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int N=1e5+5,oo=1e9+5;
inline int read() {
int x=0,flag=0;char ch=getchar();
while(ch<'0'||ch>'9') {flag|=(ch=='-');ch=getchar();}
while('0'<=ch&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return flag?-x:x;
}
inline int mx(int x,int y) {return x>y?x:y;}
inline int mn(int x,int y) {return x<y?x:y;}
inline void swp(int &x,int &y) {x^=y^=x^=y;}
inline int as(int x) {return x>0?x:-x;}
int n,b[N<<1],val[N<<1],Val[N<<1],lim[N<<1],vc[N],Vc[N],ans;
int f[N<<1][20],to[N<<1];
struct Node {
int l,r;
bool operator <(const Node &w) {
return r<w.r;
}
}a[N];
int main() {
int TT=read();
while(TT--) {
n=read();vc[0]=Vc[0]=b[0]=0;
for(int i=1;i<=n;++i) a[i].l=read(),a[i].r=read(),b[++b[0]]=a[i].l,b[++b[0]]=a[i].r;
sort(b+1,b+b[0]+1);b[0]=unique(b+1,b+b[0]+1)-b-1;
for(int i=1;i<=n;++i) a[i].l=lower_bound(b+1,b+b[0]+1,a[i].l)-b,a[i].r=lower_bound(b+1,b+b[0]+1,a[i].r)-b;
sort(a+1,a+n+1);
int pre=-oo;
for(int i=1;i<=n;++i) if(pre<a[i].l) {
pre=a[i].r;
vc[++vc[0]]=pre;
}
ans=0;
for(int i=1,p1,p2;i<=n;++i) {
p1=lower_bound(vc+1,vc+vc[0]+1,a[i].l)-vc;
p2=upper_bound(vc+1,vc+vc[0]+1,a[i].r)-vc-1;
ans=mx(ans,p2-p1+1);
}
for(int i=1;i<=b[0]+1;++i) val[i]=Val[i]=b[0]+1,lim[i]=0;
for(int i=1;i<=n;++i) val[a[i].l]=mn(val[a[i].l],a[i].r),Val[a[i].l]=a[i].l,lim[a[i].l]=mx(lim[a[i].l],a[i].r);
for(int i=b[0]-1;i>=1;--i) val[i]=mn(val[i],val[i+1]),Val[i]=mn(Val[i],Val[i+1]);
for(int i=2;i<=b[0];++i) lim[i]=mx(lim[i-1],lim[i]);
for(int i=1;i<=b[0]+1;++i) f[i][0]=val[i+1];
f[b[0]+1][0]=b[0]+1;
for(int j=1;j<=17;++j)
for(int i=1;i<=b[0]+1;++i)
f[i][j]=f[f[i][j-1]][j-1];
for(int i=1;i<=b[0];++i) {
int now=i;
for(int j=17;j>=0;--j)
if(((ans-1)>>j)&1) now=f[now][j];
to[i]=now;
}
int pos=1;
while(pos<=b[0]) {
if(lim[pos]<to[pos]&&(Vc[0]<ans-1||lim[Vc[Vc[0]-(ans-1)+1]]<pos)) {
Vc[++Vc[0]]=pos;
pos=Val[pos+1];
} else ++pos;
}
bool fl=1;
for(int i=1,p1,p2;i<=n;++i) {
p1=lower_bound(Vc+1,Vc+Vc[0]+1,a[i].l)-Vc;
p2=upper_bound(Vc+1,Vc+Vc[0]+1,a[i].r)-Vc-1;
if(p2-p1+1==0) fl=0;
}
if(fl) {
printf("%d %d ",ans-1,Vc[0]);
for(int i=1;i<=Vc[0];++i) printf("%d ",b[Vc[i]]);
printf("\n");
} else {
printf("%d %d ",ans,vc[0]);
for(int i=1;i<=vc[0];++i) printf("%d ",b[vc[i]]);
printf("\n");
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 7652kb
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 4 4 4 10 30 50 70 3 3 -7 -1 9 2 3 1 3 5
result:
wrong answer test 3: expected 2, found 3