oj.uz

답안 #751856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751856 2023-06-01T16:30:06 Z 1075508020060209tc 서열 (APIO23_sequence) C++17
0 / 100
 872 ms 54200 KB 
#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++){
        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];
        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;
            }
        }
        upd(1,vpl[i][0],n,2);
        upd(1,vpl[i][1],n,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];
        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;
            }
        }
        upd(1,vpl[i][0],n,2);
        upd(1,vpl[i][1],n,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;
}



*/

Compilation message

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

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Incorrect 6 ms 11932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Incorrect 6 ms 11932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Incorrect 49 ms 17840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 11932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 872 ms 54092 KB Output is correct
2 Correct 836 ms 54200 KB Output is correct
3 Correct 295 ms 53556 KB Output is correct
4 Correct 290 ms 53512 KB Output is correct
5 Incorrect 847 ms 50188 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Incorrect 6 ms 11932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Incorrect 6 ms 11932 KB Output isn't correct
3 Halted 0 ms 0 KB -