제출 #751859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751859		1075508020060209tc	서열 (APIO23_sequence)	C++17	13 / 100	876 ms	54092 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int lowbit(int x){return x&-x;}

struct BIT{
vector<int>bit;
int MX;
void init(int len){
for(int i=0;i<=len+100;i++){
    bit.push_back(0);
}
MX=len;
}
void upd(int pl,int vl){
while(pl<=MX){
    bit[pl]+=vl;
    pl+=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}
int k_th(int k){
int lg=__lg(MX);
int cnt=0;
int nw=0;
for(int i=lg;i>=0;i--){
    if(cnt+bit[nw+(1<<i)]<k){
        nw+=(1<<i);
        cnt+=bit[nw];
    }
}
return nw+1;
}
};


int n;
int ar[500005];

struct SGTR{
int l;int r;
int mx;int mn;
int lz;
}tr[2000056];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].mx=0;tr[nw].mn=0;
tr[nw].lz=0;
if(l==r){
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}
void psh(int nw){
int ad=tr[nw].lz;
tr[nw].lz=0;
tr[nw*2].lz+=ad;tr[nw*2+1].lz+=ad;
tr[nw*2].mx+=ad;tr[nw*2+1].mx+=ad;
tr[nw*2].mn+=ad;tr[nw*2+1].mn+=ad;
}
void upd(int nw,int l,int r,int v){
if(tr[nw].l>=l&&tr[nw].r<=r){
    tr[nw].mx+=v;tr[nw].mn+=v;
    tr[nw].lz+=v;
    return;
}
if(tr[nw].l>r||tr[nw].r<l){
    return;
}
if(tr[nw].lz){
    psh(nw);
}
upd(nw*2,l,r,v);
upd(nw*2+1,l,r,v);
tr[nw].mx=max(tr[nw*2].mx,tr[nw*2+1].mx);
tr[nw].mn=min(tr[nw*2].mn,tr[nw*2+1].mn);
}
int qmx(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
    return tr[nw].mx;
}
if(tr[nw].l>r||tr[nw].r<l){
    return -1e9;
}
if(tr[nw].lz){
    psh(nw);
}
return max(qmx(nw*2,l,r),qmx(nw*2+1,l,r));
}
int qmn(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
    return tr[nw].mn;
}
if(tr[nw].l>r||tr[nw].r<l){
    return 1e9;
}
if(tr[nw].lz){
    psh(nw);
}
return min(qmn(nw*2,l,r),qmn(nw*2+1,l,r));
}

vector<int>vpl[500005];


int slv(){

    for(int i=1;i<=n-1;i++){
        if(ar[i]==ar[i+1]){
            return 2;
        }
    }
    for(int i=1;i<=n;i++){
        vpl[i].clear();
    }
    for(int i=1;i<=n;i++){
        vpl[ar[i]].push_back(i);
    }
    int ans=1;
    buildtr(1,1,n);
    for(int i=1;i<=n;i++){
        upd(1,i,n,-1);
    }

    /*for(int i=1;i<=n;i++){
        cout<<qmx(1,i,i)<<" ";
    }cout<<endl;*/

    for(int i=1;i<=n;i++){
        if(vpl[i].size()==0){continue;}
        if(vpl[i].size()==1){
            upd(1,vpl[i][0],n,2);
            continue;
        }
        upd(1,vpl[i][0],n,2);
        upd(1,vpl[i][1],n,2);
        int l=vpl[i][0];int r=vpl[i][1];
        int lrv=qmx(1,r,r)-((l==1)?0:qmx(1,l-1,l-1));
       // cout<<r<<" "<<qmx(1,r,r)<<"\n";
        if(lrv==1||lrv==0||lrv==2){
            return 2;
        }
        if(lrv<0){
            int rv=qmx(1,r,n);int lv= ((l==1)?0:qmn(1,1,l-1));
            lv=min(lv,0);
            if(rv-lv>=0){
                return 2;
            }
        }
    }
    //sec
    buildtr(1,1,n);
    for(int i=1;i<=n;i++){
        upd(1,i,n,-1);
    }
    for(int i=n;i>=1;i--){
        if(vpl[i].size()==0){continue;}
        if(vpl[i].size()==1){
            upd(1,vpl[i][0],n,2);
            continue;
        }
        int l=vpl[i][0];int r=vpl[i][1];
        upd(1,vpl[i][0],n,2);
        upd(1,vpl[i][1],n,2);
        int lrv=qmx(1,r,r)-((l==1)?0:qmx(1,l-1,l-1));
        if(lrv==1||lrv==0||lrv==2){
            return 2;
        }
        if(lrv<0){
            int rv=qmx(1,r,n);int lv= ((l==1)?0:qmn(1,1,l-1));
            lv=min(lv,0);
            if(rv-lv>=0){
                return 2;
            }
        }

    }
    return 1;
}


int sequence(int N, std::vector<int> A) {
    n=N;
    for(int i=0;i<n;i++){
        ar[i+1]=A[i];
    }
return slv();

  return 0;
}
/*


signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
    }
    cout<<slv();


    return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int slv()':
sequence.cpp:128:9: warning: unused variable 'ans' [-Wunused-variable]
  128 |     int ans=1;
      |         ^~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18