QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291552#7969. 套娃FamiglistmoWA 23ms44472kbC++144.6kb2023-12-26 21:55:062023-12-26 21:55:07

Judging History

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

  • [2023-12-26 21:55:07]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:44472kb
  • [2023-12-26 21:55:06]
  • 提交

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 '