Submission #1196234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196234		Mohamed_Kachef06	Sequence (APIO23_sequence)	C++20	0 / 100	229 ms	89868 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>


int sequence(int N, std::vector<int> A) {
  int X = 1e7/N; 
    int f[X+1][N+1] = {} , sf[X+1][N+1] = {};
    A.insert(A.begin() , 0); 

    for (int i = 1;  i <= N ; i++){
      f[A[i]][i]++;
      for (int j =1 ; j <= X ; j++){
        f[j][i] += f[j][i-1]; 
      }
    } 

    for (int i = 1 ; i <= N ; i++){
      for (int j = 1 ; j <= X ; j++){
        sf[j][i] = f[j][i];
        sf[j][i] += sf[j-1][i]; 
      }
    }
    int mx = 0; 

    for (int m = 1 ; m <= X ; m++){
      int v[2][N+1] = {}; 
      for (int i = 1 ; i <= N ; i++){
         for (int j = 1;  j <= X ; j++){
          v[0][i] = sf[m][i] - (sf[X][i] - sf[m-1][i]); 
          v[1][i] = (sf[X][i] - sf[m-1][i]) - sf[m-1][i]; 
         }
      }
      int suf[2][N+2] = {};
      suf[0][N+1] = -1e9;
      suf[1][N+1] = -1e9;
      for (int i = N ; i > 0 ; i--) suf[0][i] = max(suf[0][i+1] , v[0][i]); 
      for (int i = N ; i > 0 ; i--) suf[1][i] = max(suf[1][i+1] , v[1][i]); 
      for (int l = 1 ; l <= N ; l++){
          int L = l , R = N , md , ans = -1;
          while(L<=R){
            md = (L+R)/2; 
            if (suf[0][md] >= v[0][l-1] && suf[1][md] >= v[1][l-1]) L = md+1 , ans = md;
            else R = md-1; 
          }
          //cout << m << ' ' << l << ' ' << ans << ' ' << suf[0][ans] << ' ' << v[0][l-1] << '\n'; 
          if (ans != -1) mx = max(mx , f[m][ans] - f[m][l-1]);  
      }
    }
    return mx;
}

• Subtask 1: 0 / 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