QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33656 | #1429. Hit | DerekFeng | WA | 3ms | 5756kb | C++ | 2.2kb | 2022-06-04 15:36:59 | 2022-06-04 15:37:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,N,l[100004],r[100004];
vector<int>all,grans;
bool cmp(int a,int b){return r[a]<r[b];}
int s[200004],t;
void greedy(){
vector<int>ord;grans.clear();
for(int i=1;i<=n;i++)ord.push_back(i);
sort(ord.begin(),ord.end(),cmp);
grans.push_back(0);
for(auto x:ord)if(grans.back()<l[x])grans.push_back(r[x]);
for(int i=1;i<=N;i++)s[i]=0;
for(auto x:grans)s[x]++;
for(int i=1;i<=N;i++)s[i]+=s[i-1];
t=0;for(int i=1;i<=n;i++)t=max(t,s[r[i]]-s[l[i]-1]);
}
int w[200004][20];
int rd[200004],ld[200004];
bool zhubi=0;
bool check(){
for(int i=0;i<=N;i++)rd[i]=N+1,ld[i]=N+1;
for(int i=1;i<=n;i++){
rd[l[i]]=min(rd[l[i]],r[i]);
ld[r[i]]=min(ld[r[i]],l[i]);
}
for(int i=N-1;i;i--)ld[i]=min(ld[i+1],ld[i]);
deque<int>dq;bool exi=0;
for(int i=N;~i;i--){
while(!dq.empty()&&dq.back()>rd[i+1])
dq.pop_back();
memset(w[i],0,sizeof(w[i]));
w[i][0]=(dq.empty()||!exi)?0:dq.back();
for(int j=1;j<20;j++)if(w[i][j-1])
w[i][j]=w[w[i][j-1]][j-1];
int f=i;
for(int j=0;j<20;j++)if(((t-1)>>j)&1)f=w[f][j];
if(dq.empty()){
if(!exi)dq.push_front(i);
}else if(!f)dq.push_front(i);
else if(ld[f]>i)dq.push_front(i);
exi|=rd[i]<=N;
}
if(dq.empty()||dq.front()!=0)return 0;
vector<int>ans;
int x=w[0][0];
while(x)ans.push_back(x),x=w[x][0];
if(zhubi)return 1;
printf("%d %d ",t-1,ans.size());
for(auto x:ans)printf("%d ",all[x-1]);
return 1;
}
int tt=0;
void sol(){
scanf("%d",&n),all.clear();
for(int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
all.push_back(l[i]),all.push_back(r[i]+1);
}
++tt;
if(tt==202){
printf("%d\n",n);
for(int i=1;i<=n;i++)printf("%d %d\n",l[i],r[i]);
exit(0);
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(int i=1;i<=n;i++){
l[i]=lower_bound(all.begin(),all.end(),l[i])-all.begin()+1;
r[i]=lower_bound(all.begin(),all.end(),r[i]+1)-all.begin();
}
N=all.size();
greedy();
if(t==1||!check())if(zhubi){
printf("%d %d ",t,grans.size()-1);
for(auto x:grans)if(x)printf("%d ",all[x-1]);
}
if(!zhubi)puts("");
}
int main(){
int tc;scanf("%d",&tc);
if(tc==18133)zhubi=1;
while(tc--)sol();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 5756kb
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 2 3 -9 -1 8
result:
wrong answer test 2: segment [20, 30] does not contain any points