Submission #1229295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229295		pera	Sequence (APIO23_sequence)	C++20	28 / 100	2096 ms	41288 KiB

sequence

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


int sequence(int N, std::vector<int> a) {
   vector<int> A(N + 1);
   for(int i = 1;i <= N;i ++){
      A[i] = a[i - 1];
   }
   vector<vector<int>> occ(N + 1);
   for(int i = 1;i <= N;i ++){
      occ[A[i]].emplace_back(i);
   }

   vector<int> mn(N + 1) , mx(N + 1);
   vector<int> pref_mn(N + 1) , pref_mx(N + 1);

   auto set_mn = [&](int pos , int x){
      mn[pos] = x;
      for(int i = 0;i <= N;i ++){
         pref_mn[i] = mn[i] + (i > 0 ? pref_mn[i - 1] : 0);
      }
   };

   auto set_mx = [&](int pos , int x){
      mx[pos] = x;
      for(int i = 0;i <= N;i ++){
         pref_mx[i] = mx[i] + (i > 0 ? pref_mx[i - 1] : 0);
      }
   };

   auto find_min = [&](int L , int R){
      int best = pref_mn[L];
      for(int i = L;i <= R;i ++){
         best = min(best , pref_mn[i]);
      }
      return best;
   };

   auto find_max = [&](int L , int R){
      int best = pref_mx[L];
      for(int i = L;i <= R;i ++){
         best = max(best , pref_mx[i]);
      }
      return best;
   };

   auto check = [&](int L , int R , int v){
      int lmin = find_min(0 , L - 1);
      int lmax = find_max(0 , L - 1);
      int rmin = find_min(R , N);
      int rmax = find_max(R , N);

      int val_min = (rmin - pref_mn[R]) + (pref_mx[R] - pref_mx[L - 1]) + (pref_mx[L - 1] - lmax);
      int val_max = (rmax - pref_mx[R]) + (pref_mx[R] - pref_mx[L - 1]) + (pref_mn[L - 1] - lmin);
      
      return !(val_max < -v || v < val_min);
   };

   for(int i = 1;i <= N;i ++){
      set_mn(i , +1);
      set_mx(i , +1);
   }

   int ans = 0;

   for(int v = 1;v <= N;v ++){
      auto &t = occ[v];
      for(int x : t){
         set_mn(x , -1);
      }
      int r = -1;
      for(int i = 0;i < (int)t.size();i ++){
         while(r + 1 < (int)t.size()){
            ++r;
            set_mn(t[r] , 0);
            set_mx(t[r] , 0);
            if(!check(t[i] , t[r] , r - i + 1)){
               set_mn(t[r] , -1);
               set_mx(t[r] , +1);
               --r;
               break;
            }
         }
         ans = max(ans , r - i + 1);
         set_mn(t[i] , -1);
         set_mx(t[i] , +1);
      }
      for(int x : t){
         set_mn(x , -1);
         set_mx(x , -1);
      }
   }
   return ans;
}

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