Submission #751850

#	Time	Username	Problem	Language	Result	Execution time	Memory
751850		1075508020060209tc	Sequence (APIO23_sequence)	C++17	7 / 100	88 ms	12128 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];
int freq[500005];
int lpl[500005];
int rpl[500005];

int far[500005];

int slv(){
   int ans=0;
   for(int i=1;i<=n;i++){
        lpl[i]=0;rpl[i]=0;
        freq[i]=0;
   }
   for(int i=1;i<=n;i++){
        freq[ar[i]]++;
        if(lpl[ar[i]]==0){
            lpl[ar[i]]=i;
        }
        rpl[ar[i]]=i;
   }

   for(int i=1;i<=n;i++){
        int it=i;
        while(it+1<=n&&ar[it+1]==ar[i]){it++;}
        ans=max(ans,it-i+1);
        i=it;
   }
   for(int i=1;i<=n;i++){
        if(freq[i]==0){continue;}
        int len=rpl[i]-lpl[i]+1;
        int r=rpl[i];int l=lpl[i];
        int f=freq[i];
        if((f+l-1+n-r)>=len-f){
            ans=max(ans,f);
        }
   }
   return 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];
    }
return slv();

  return 0;
}

/*

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


    return 0;
}


*/

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