Submission #1229317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229317		pera	Sequence (APIO23_sequence)	C++20	57 / 100	2096 ms	72840 KiB

sequence

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


const int N = 5E5 + 2;

int t_mn[4 * N] , t_mx[4 * N];
int lzn[4 * N] , lzx[4 * N];

void push_mn(int u){
   t_mn[u * 2] += lzn[u];
   t_mn[u * 2 + 1] += lzn[u];
   lzn[u * 2] += lzn[u];
   lzn[u * 2 + 1] += lzn[u];
   lzn[u] = 0;
}

void update_mn(int u , int l , int r , int L , int R , int x){
   if(l > r || r < L || l > R){
      return;
   }
   if(L <= l && r <= R){
      t_mn[u] += x;
      lzn[u] += x;
      return;
   }
   int m = (l + r) / 2;
   push_mn(u);
   update_mn(u * 2 , l , m , L , R , x);
   update_mn(u * 2 + 1 , m + 1 , r , L , R , x);
   t_mn[u] = min(t_mn[u * 2] , t_mn[u * 2 + 1]);
}

int query_mn(int u , int l , int r , int L , int R){
   if(l > r || r < L || l > R){
      return 1E9;
   }
   if(L <= l && r <= R){
      return t_mn[u];
   }
   push_mn(u);
   int m = (l + r) / 2;
   return min(query_mn(u * 2 , l , m , L , R) , query_mn(u * 2 + 1 , m + 1 , r , L , R));
}

void push_mx(int u){
   t_mx[u * 2] += lzx[u];
   t_mx[u * 2 + 1] += lzx[u];
   lzx[u * 2] += lzx[u];
   lzx[u * 2 + 1] += lzx[u];
   lzx[u] = 0;
}

void update_mx(int u , int l , int r , int L , int R , int x){
   if(l > r || r < L || l > R){
      return;
   }
   if(L <= l && r <= R){
      t_mx[u] += x;
      lzx[u] += x;
      return;
   }
   int m = (l + r) / 2;
   push_mx(u);
   update_mx(u * 2 , l , m , L , R , x);
   update_mx(u * 2 + 1 , m + 1 , r , L , R , x);
   t_mx[u] = max(t_mx[u * 2] , t_mx[u * 2 + 1]);
}

int query_mx(int u , int l , int r , int L , int R){
   if(l > r || r < L || l > R){
      return -1E9;
   }
   if(L <= l && r <= R){
      return t_mx[u];
   }
   push_mx(u);
   int m = (l + r) / 2;
   return max(query_mx(u * 2 , l , m , L , R) , query_mx(u * 2 + 1 , m + 1 , r , L , R));
}

int sequence(int N, std::vector<int> a) {
   for(int i = 0;i < 4 * (N + 1);i ++){
      t_mn[i] = t_mx[i] = lzn[i] = lzx[i] = 0;
   }

   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);
      // }
      update_mn(1 , 1 , N + 1 , pos + 1 , N + 1 , x - mn[pos]);
      mn[pos] = x;
   };

   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);
      // }
      update_mx(1 , 1 , N + 1 , pos + 1 , N + 1 , x - mx[pos]);
      mx[pos] = x;
   };

   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;
      return query_mn(1 , 1 , N + 1 , L + 1 , R + 1);
   };

   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;
      return query_mx(1 , 1 , N + 1 , L + 1 , R + 1);
   };

   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 nR = find_min(R , R) , nL = find_min(L - 1 , L - 1);
      int xR = find_max(R , R) , xL = find_max(L - 1 , L - 1);

      int val_min = (rmin - nR) + (nR - nL) + (xL - lmax);
      int val_max = (rmax - xR) + (xR - xL) + (nL - 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: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 22 / 22
• Subtask 7: 0 / 18