oj.uz

Submission #751850

# Submission time Handle Problem Language Result Execution time Memory
751850 2023-06-01T15:52:17 Z 1075508020060209tc Sequence (APIO23_sequence) C++17
7 / 100
 88 ms 12128 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];
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.0 / 11.0

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

Subtask #2
0.0 / 17.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 56 ms 12000 KB Output is correct
3 Correct 88 ms 11988 KB Output is correct
4 Correct 39 ms 11988 KB Output is correct
5 Correct 59 ms 12052 KB Output is correct
6 Correct 61 ms 12000 KB Output is correct
7 Correct 42 ms 12000 KB Output is correct
8 Correct 49 ms 11988 KB Output is correct
9 Correct 50 ms 12128 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 45 ms 12000 KB Output is correct
3 Incorrect 45 ms 12000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

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

Subtask #6
0.0 / 22.0

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

Subtask #7
0.0 / 18.0

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