Submission #1230229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230229		pera	Sequence (APIO23_sequence)	C++20	100 / 100	1800 ms	68920 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

const int N = 5E5 + 2;

struct node{
   int mx , mn , lz0 = 0 , lz1 = 0;
} t[4 * N];

node neut = {(int)-1E9 , (int)1E9 , 0 , 0};

node join(node x , node y){
   node z;
   z.mx = max(x.mx , y.mx);
   z.mn = min(x.mn , y.mn);
   return z;
}

void build(int u , int l , int r){
   if(l == r){
      t[u].mx = t[u].mn = r - 1;
      return;
   }
   int m = (l + r) / 2;
   build(u * 2 , l , m);
   build(u * 2 + 1 , m + 1 , r);
   t[u] = join(t[u * 2] , t[u * 2 + 1]);
}

void push(int u){
   t[u * 2].mn += t[u].lz0;
   t[u * 2 + 1].mn += t[u].lz0;
   t[u * 2].lz0 += t[u].lz0;
   t[u * 2 + 1].lz0 += t[u].lz0;
   t[u].lz0 = 0;

   t[u * 2].mx += t[u].lz1;
   t[u * 2 + 1].mx += t[u].lz1;
   t[u * 2].lz1 += t[u].lz1;
   t[u * 2 + 1].lz1 += t[u].lz1;
   t[u].lz1 = 0;
}

void update(int u , int l , int r , int L , int R , int x , int w){
   if(l > r || r < L || l > R){
      return;
   }
   if(L <= l && r <= R){
      if(w == 0){
         t[u].mn += x;
         t[u].lz0 += x;
      }else{
         t[u].mx += x;
         t[u].lz1 += x;
      }
      return;
   }
   push(u);
   int m = (l + r) / 2;
   update(u * 2 , l , m , L , R , x , w);
   update(u * 2 + 1 , m + 1 , r , L , R , x , w);
   t[u] = join(t[u * 2] , t[u * 2 + 1]);
}


node query(int u , int l , int r , int L , int R){
   if(l > r || r < L || l > R){
      return neut;
   }
   if(L <= l && r <= R){
      return t[u];
   }
   push(u);
   int m = (l + r) / 2;
   return join(query(u * 2 , l , m , L , R) , query(u * 2 + 1 , m + 1 , r , L , R));
}


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

   auto get= [&](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(1 , 1 , N + 1 , L + 1 , R + 1);
   };


   auto check = [&](int L , int R , int v){
      node dL = get(0 , L - 1);
      int lmin = dL.mn , lmax = dL.mx;

      node dR = get(R , N);
      int rmin = dR.mn , rmax = dR.mx;

      node onL = get(L - 1 , L - 1);
      int nL = onL.mn , xL = onL.mx;

      node onR = get(R , R);
      int nR = onR.mn , xR = onR.mx;

      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);
   };

   build(1 , 1 , N + 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;
      bool is_done = false;
      for(int i = 0;i < (int)t.size();i ++){
         while(r + 1 < (int)t.size()){
            ++r;
            if(!is_done){   
               set_mn(t[r] , 0);
               set_mx(t[r] , 0);
               is_done = true;
            }
            if(!check(t[i] , t[r] , r - i + 1)){
               --r;
               break;
            }
            is_done = false;
         }
         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: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18