Submission #789766

#	Time	Username	Problem	Language	Result	Execution time	Memory
789766		1075508020060209tc	Sequence (APIO23_sequence)	C++17	100 / 100	1173 ms	152004 KiB

sequence

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

vector<int>vpl[500005];
vector<int>vplv[500005];
int ar[500005];
int n;
struct SEGMENT_TREE{

struct SGTR{
int l;int r;
int lz;
int mx;int mn;
};
vector<SGTR>tr;
void init(int n){
for(int i=0;i<=n*4+10;i++){
    tr.push_back({0,0,0,0,0});
}
}


void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].lz=0;tr[nw].mx=0;tr[nw].mn=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 v){
if(tr[nw].l>=l){
    tr[nw].mx+=v;
    tr[nw].mn+=v;
    tr[nw].lz+=v;
    return;
}
if(tr[nw].r<l){return;}
if(tr[nw].lz){psh(nw);}
upd(nw*2,l,v);
upd(nw*2+1,l,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));
}

};

SEGMENT_TREE A;
SEGMENT_TREE B;

int ok(int l,int r){
int rv=A.qmx(1,r,n);
int lv=(l==1)?0:A.qmn(1,1,l-1);
lv=min(lv,0);
if(rv-lv<0){return 0;}
rv=B.qmx(1,r,n);
lv=(l==1)?0:B.qmn(1,1,l-1);
lv=min(lv,0);
if(rv-lv<0){return 0;}
return 1;
}

int fslv(){
    //cin>>n;
    for(int i=1;i<=n;i++){
      //  cin>>ar[i];
        vpl[ar[i]].push_back(i);
    }
    int ans=1;
    A.init(n);
    B.init(n);
    A.buildtr(1,1,n);
    B.buildtr(1,1,n);
    for(int i=1;i<=n;i++){
        A.upd(1,i,-1);
        B.upd(1,i,1);
    }
    for(int nw=1;nw<=n;nw++){
        for(int i=0;i<vpl[nw].size();i++){
            A.upd(1,vpl[nw][i],2);
        }
        int lit=0;
        for(int i=0;i<vpl[nw].size();i++){
            while(!ok(vpl[nw][lit],vpl[nw][i])){lit++;}
            ans=max(ans,i-lit+1);
        }
        for(int i=0;i<vpl[nw].size();i++){
            B.upd(1,vpl[nw][i],-2);
        }
    }
   // cout<<ans;
return ans;

}


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

  return 0;
}
/*

signed main()
{




    return 0;
}

*/

Compilation message (stderr)

sequence.cpp: In function 'int fslv()':
sequence.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i=0;i<vpl[nw].size();i++){
      |                     ~^~~~~~~~~~~~~~~
sequence.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int i=0;i<vpl[nw].size();i++){
      |                     ~^~~~~~~~~~~~~~~
sequence.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for(int i=0;i<vpl[nw].size();i++){
      |                     ~^~~~~~~~~~~~~~~

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