QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291552 | #7969. 套娃 | Famiglistmo | WA | 23ms | 44472kb | C++14 | 4.6kb | 2023-12-26 21:55:06 | 2023-12-26 21:55:07 |
Judging History
answer
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<21],*p1=buf,*p2=buf;
const long long _base=107374183;
int writetemp[30];
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;
return x;
}
inline void write(int x)
{
int t;
int tot=(x==0);
writetemp[1]=0;
while(x) t=x/10,writetemp[++tot]=x-(t<<1)-(t<<3),x=t;
for(int i=tot;i>=1;i--) putchar(writetemp[i]+'0');
putchar('\n');
return ;
}
int n,tot;
int a[1000010],tax[1000010];
vector<int> pos[1000010];
int maxl[1000010],minr[1000010];
struct offline
{
int x,val,num;
}c[1000010];
bool cmp(offline a,offline b)
{
return a.x<b.x;
}
set<pair<int,int> > now,nxt;
set<int> s;
// void addoff(int l,int r,int val)
// {
// if(l>r) return ;
// c[++tot]=(offline){l,val,1};
// c[++tot]=(offline){r+1,val,-1};
// return ;
// }
int get_pos(int i,int x)
{
if(x<0) return 0;
if(x>=pos[i].size()) return n+1;
return pos[i][x];
}
void add(int x)
{
tax[x]++,s.erase(x);
return ;
}
void del(int x)
{
tax[x]--;
if(tax[x]==0) s.insert(x);
return ;
}
const int N=1e5+5;
struct Tree{
int mn,mnp;
}t[N<<2];
void pushup(int rt){
t[rt].mn=min(t[ls].mn,t[rs].mn);
if(t[rt].mn==t[rs].mn)t[rt].mnp=t[rs].mnp;
if(t[rt].mn==t[ls].mn)t[rt].mnp=t[ls].mnp;
}
void build(int l,int r,int rt){
if(l==r)return t[rt].mnp=l,void();
build(l,mid,ls),build(mid+1,r,rs),pushup(rt);
}
void alter(int l,int r,int rt,int id,int v){
if(l==r)return t[rt].mn+=v,void();
if(id<=mid)alter(l,mid,ls,id,v);
else alter(mid+1,r,rs,id,v);
pushup(rt);
}
int mn[N],mx[N];
void addoff(int l,int r,int val)
{
if(l>r) return ;
mn[val]=min(mn[val],l);
mx[val]=max(mx[val],r);
return ;
}
vector<int>A[N],B[N];
int main()
{
// freopen("s.out","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]].push_back(i);
for(int i=0;i<=n;++i)
mn[i]=n+1,mx[i]=0;
if(pos[0].empty())
{
for(int i=1;i<=n;i++) printf("%d ",1);
printf("\n");
return 0;
}
for(int i=0;i<pos[0].size();i++)
{
if(i==0) addoff(1,pos[0][i]-1,0);
if(i==pos[0].size()-1) addoff(1,n-pos[0][i],0);
else addoff(1,pos[0][i+1]-pos[0][i]-1,0);
now.insert(make_pair(pos[0][i],pos[0][i]));
}
for(int i=1;i<=n+1;i++)
{
// printf("%d\n",i);
for(int j=0;j<pos[i].size();j++) minr[j]=n+1,maxl[j]=0;
for(set<pair<int,int> >::iterator nowpos=now.begin();nowpos!=now.end();nowpos++)
{
int l=lower_bound(pos[i].begin(),pos[i].end(),(*nowpos).first)-pos[i].begin()-1;
int r=upper_bound(pos[i].begin(),pos[i].end(),(*nowpos).second)-pos[i].begin();
if(r-l==1)
{
addoff((*nowpos).second-(*nowpos).first+1,get_pos(i,r)-get_pos(i,l)-1,i);
if(l>=0) minr[l]=min(minr[l],(*nowpos).second);
if(r<pos[i].size()) maxl[r]=max(maxl[r],(*nowpos).first);
}
else
{
nxt.insert(make_pair((*nowpos).first,(*nowpos).second));
}
}
for(int j=0;j<pos[i].size();j++)
{
int nowpos=pos[i][j];
if(maxl[j]) nxt.insert(make_pair(maxl[j],nowpos));
if(minr[j]!=n+1) nxt.insert(make_pair(nowpos,minr[j]));
}
swap(now,nxt);
nxt.clear();
}
for(int i=0;i<=n;++i)
if(mn[i]<=mx[i])
A[mn[i]].push_back(i),
B[mx[i]+1].push_back(i);
build(0,n+1,1);
for(int i=1;i<=n;++i){
for(auto x:A[i])alter(0,n+1,1,x,1);
for(auto x:B[i])alter(0,n+1,1,x,-1);
cout<<t[1].mnp<<' ';
assert(t[1].mn==0);
}
// for(int i=0;i<=n+1;i++) s.insert(i);
// sort(c+1,c+tot+1,cmp);
// int now=1;
// for(int i=1;i<=n;i++)
// {
// while(now<=tot&&c[now].x==i)
// {
// if(c[now].num==1) add(c[now].val);
// else del(c[now].val);
// now++;
// }
// printf("%d ",*s.begin());
// }
// printf("\n");
return 0;
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 43784kb
input:
6 0 0 0 1 2 3
output:
2 3 4 0 0 0
result:
ok single line: '2 3 4 0 0 0 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 44472kb
input:
100 0 10 21 9 4 1 14 0 8 1 4 6 10 0 0 4 18 0 12 5 2 5 15 1 6 2 0 4 14 5 1 2 23 1 8 1 24 8 8 9 5 2 12 2 3 7 6 11 12 12 6 12 4 4 5 0 7 4 9 12 1 7 4 7 12 2 10 2 4 8 7 1 4 0 13 9 13 2 2 3 9 14 7 9 15 10 10 6 2 12 3 11 6 3 4 7 9 6 11 1
output:
2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok single line: '2 2 3 4 4 4 4 4 4 4 4 4 4 4 4 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '
Test #3:
score: -100
Wrong Answer
time: 23ms
memory: 44440kb
input:
100000 127 145 474 139 36 135 75 670 76 433 206 214 283 56 214 440 147 280 244 190 181 565 31 550 261 93 526 404 125 390 17 552 5 364 53 337 52 506 277 279 15 248 46 61 826 69 166 297 171 289 150 175 111 151 317 342 166 13 199 152 308 19 156 347 205 166 45 115 177 235 422 425 109 4 658 232 347 370 4...
output:
2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ...
result:
wrong answer 1st lines differ - expected: '2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '