Submission #791393

#	Time	Username	Problem	Language	Result	Execution time	Memory
791393		tkm_algorithms	Sequence (APIO23_sequence)	C++17	11 / 100	2070 ms	54092 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];
int ar[500005];
int n;
struct SGTR{
int l;int r;
int lz;
int mx;int mn;
}tr[2000006];
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));
}
 
 
 
 
int ok(int K){
buildtr(1,1,n);
for(int i=1;i<=n;i++){
    upd(1,i,-1);
}
for(int i=1;i<=n;i++){
    for(int j=0;j<vpl[i].size();j++){
        upd(1,vpl[i][j],2);
    }
    for(int j=K-1;j<vpl[i].size();j++){
        int lpl=vpl[i][j-K+1];int rpl=vpl[i][j];
        if( ((rpl-lpl+1)-K)<=K ){return 1;}
        int rv=qmx(1,rpl,rpl);int lv=(lpl==1)?0:qmx(1,lpl-1,lpl-1);
        if(rv==0||rv==1){return 1;}
        if(rv<0){
            int lmn=(lpl==1)?0:qmn(1,1,lpl-1);
            int rmx=qmx(1,rpl,n);
            if(rmx-lmn>=0){
                return 1;
            }
        }
    }
}
 
 
buildtr(1,1,n);
for(int i=1;i<=n;i++){
    upd(1,i,-1);
}
for(int i=n;i>=1;i--){
    for(int j=0;j<vpl[i].size();j++){
        upd(1,vpl[i][j],2);
    }
    for(int j=K-1;j<vpl[i].size();j++){
        int lpl=vpl[i][j-K+1];int rpl=vpl[i][j];
        if( ((rpl-lpl+1)-K)<=K ){return 1;}
        int rv=qmx(1,rpl,rpl);int lv=(lpl==1)?0:qmx(1,lpl-1,lpl-1);
        if(rv==0||rv==1){return 1;}
        if(rv<0){
            int lmn=(lpl==1)?0:qmn(1,1,lpl-1);
            int rmx=qmx(1,rpl,n);
            if(rmx-lmn>=0){
                return 1;
            }
        }
    }
}
return 0;
}
 
int fslv(){
    //cin>>n;
    for(int i=1;i<=n;i++){
     //   cin>>ar[i];
        vpl[ar[i]].push_back(i);
    }
int ans=1;
 
for(int i=n;i>=1;i--){
    ans=max(ans,ok(i)*i);
    if(ans>1){return i;}
}
return ans;
    int l=1;int r=n;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if(ok(mi)){
            l=mi;
        }else{
            r=mi-1;
        }
    }
//    cout<<l<<endl;
    return l;
 
}
 
int sequence(int N, std::vector<int> A) {
    n=N;
    for(int i=0;i<n;i++){
        ar[i+1]=A[i];
    }
return fslv();
 
  return 0;
}
 
/*
signed main()
{
 
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
        vpl[ar[i]].push_back(i);
    }
 
    int l=1;int r=n;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if(ok(mi)){
            l=mi;
        }else{
            r=mi-1;
        }
    }
    cout<<l<<endl;
 
 
 
 
    return 0;
}
 
*/

Compilation message (stderr)

sequence.cpp: In function 'int ok(int)':
sequence.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=0;j<vpl[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
sequence.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int j=K-1;j<vpl[i].size();j++){
      |                   ~^~~~~~~~~~~~~~
sequence.cpp:77:35: warning: unused variable 'lv' [-Wunused-variable]
   77 |         int rv=qmx(1,rpl,rpl);int lv=(lpl==1)?0:qmx(1,lpl-1,lpl-1);
      |                                   ^~
sequence.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int j=0;j<vpl[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
sequence.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int j=K-1;j<vpl[i].size();j++){
      |                   ~^~~~~~~~~~~~~~
sequence.cpp:101:35: warning: unused variable 'lv' [-Wunused-variable]
  101 |         int rv=qmx(1,rpl,rpl);int lv=(lpl==1)?0:qmx(1,lpl-1,lpl-1);
      |                                   ^~

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