oj.uz

Submission #751859

# Submission time Handle Problem Language Result Execution time Memory
751859 2023-06-01T16:40:05 Z 1075508020060209tc Sequence (APIO23_sequence) C++17
13 / 100
 876 ms 54092 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++){
        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;
}
*/

Compilation message

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

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Incorrect 6 ms 11988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Incorrect 6 ms 11988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Incorrect 50 ms 17836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 54092 KB Output is correct
2 Correct 803 ms 54084 KB Output is correct
3 Correct 282 ms 53476 KB Output is correct
4 Correct 287 ms 53524 KB Output is correct
5 Correct 354 ms 50104 KB Output is correct
6 Correct 876 ms 50180 KB Output is correct
7 Correct 767 ms 48976 KB Output is correct
8 Correct 652 ms 48672 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Incorrect 6 ms 11988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Incorrect 6 ms 11988 KB Output isn't correct
3 Halted 0 ms 0 KB -