Submission #1228424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228424		pera	Sequence (APIO23_sequence)	C++20	0 / 100	2106 ms	280228 KiB

sequence

#include "sequence.h"

#include<bits/stdc++.h>
using namespace std;int sequence(int N, std::vector<int> a) {
   vector<vector<int>> occ(N + 1);
   vector<int> A(N + 1);
   for(int i = 0;i < N;i ++){
      A[i + 1] = a[i];
   }
   for(int i = 1;i <= N;i ++){
      occ[A[i]].emplace_back(i); 
   }
   //segtree 1
   //a[i] > x -> 1
   //a[i] = x -> 1
   //a[i] < x -> -1

   //segtree 2
   //a[i] > x -> 1
   //a[i] = x -> -1
   //a[i] < x -> -1

   vector<vector<int>> stw(N + 1 , vector<int>(2 , +1));
   vector<vector<int>> lz(4 * N , vector<int>(2));
   vector<vector<int>> st(4 * N , vector<int>(2));

   auto join = [&](int x , int y , int w){
      if(w == 0){
         return max(x , y);
      }
      return min(x , y);
   };

   function<void(int , int , int)> build = [&](int u , int l , int r){
      if(l == r){
         for(int w = 0;w < 2;w ++){
            st[u][w] = r - 1;
         }
         return;
      }
      int m = (l + r) / 2;
      build(u * 2 , l , m);
      build(u * 2 + 1 , m + 1 , r);
      for(int w = 0;w < 2;w ++){
         st[u][w] = join(st[u * 2][w] , st[u * 2 + 1][w] , w);
      }
   };
   
   build(1 , 1 , N + 1);

   auto push = [&](int u , int w){
      st[u * 2][w] += lz[u][w];
      st[u * 2 + 1][w] += lz[u][w];
      lz[u * 2][w] += lz[u][w];
      lz[u * 2 + 1][w] += lz[u][w];
      lz[u][w] = 0;
   };

   function<void(int , int , int , int , int , int , int)> update = [&](int w , 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){
         st[u][w] += x;
         lz[u][w] += x;
         return;
      }
      push(u , w);
      int m = (l + r) / 2;
      update(w , u * 2 , l , m , L , R , x);
      update(w , u * 2 + 1 , m + 1 , r , L , R , x);
      st[u][w] = join(st[u * 2][w] , st[u * 2 + 1][w] , w);
   };

   function<int(int , int , int , int , int , int)> query = [&](int w , int u , int l , int r , int L , int R){
      /*if(l > r || r < L || l > R){
         return (int)(w ? 1E9 : -1E9);
      }
      if(L <= l && r <= R){
         return st[u][w];
      }
      push(u , w);
      int m = (l + r) / 2;
      return join(query(w , u * 2 , l , m , L , R) , query(w , u * 2 + 1 , m + 1 , r , L , R) , w);*/
      --L , --R;
      int s = 0 , best = (w ? -1E9 : 1E9);
      for(int i = 0;i <= N;i ++){
         s += stw[i][w];
         if(L <= i && i <= R){
            if(w){
               best = max(best , s);
            }else{
               best = min(best , s);
            }
         }
      }
      return best;
   };

   auto set = [&](int w , int pos , int val){
      update(w , 1 , 1 , N + 1 , pos + 1 , N + 1 , val - stw[pos][w]);
      stw[pos][w] = val;
   };

   auto check = [&](int l , int r , int v){
      int lmax = query(1 , 1 , 1 , N + 1 , 1 , l);
      int rmax = query(1 , 1 , 1 , N + 1 , r + 1 , N + 1);
      int lmin = query(0 , 1 , 1 , N + 1 , 1 , l);
      int rmin = query(0 , 1 , 1 , N + 1 , r + 1 , N + 1);
      int val_min = rmin - lmax;
      int val_max = rmax - lmin;
      // cout << "checking " << l << " " << r << " " << v << '\n';
      // cout << val_min << " " << val_max << '\n';
      // cout << lmin << " " << lmax << " " << rmin << " " << rmax << '\n';
      // if(l == 3 && r == 8){
      //    for(int i = 1;i <= N;i ++){
      //       cout << stw[i][0] << " ";
      //    }
      //    cout << '\n';
      //    for(int i = 1;i <= N;i ++){
      //       cout << stw[i][1] << ' ';
      //    }
      //    cout << '\n';
      // }
      return !(val_max < -v || val_min > v);
   };

   int ans = 0;
   for(int i = 1;i <= N;i ++){
      for(int x : occ[i]){
         set(0 , x , 1);
         set(1 , x , -1);
      }
      // cout << "CURRENT VAL: " << i << '\n';
      int r = -1;
      for(int j = 0;j < (int)occ[i].size();j ++){
         while(r + 1 < (int)occ[i].size()){
            ++r;
            set(0 , occ[i][r] , 0);
            set(1 , occ[i][r] , 0);
            if(!check(occ[i][j] , occ[i][r] , r - j + 1)){
               set(0 , occ[i][r] , 1);
               set(1 , occ[i][r] , -1);
               --r;
               break;
            }
            // cout << "r moved" << '\n';
         }
         // cout << j << " -> " << r << '\n';
         ans = max(ans , r - j + 1);
         // if(r - j + 1 == 3){
         //    cout << "AAAQQQQ" << '\n';
         // }
         set(0 , occ[i][j] , 1);
         set(1 , occ[i][j] , -1);
      }
      //  cout << '\n';
      //  cout<< '\n';
      for(int x : occ[i]){
         set(0 , x , -1);
         set(1 , x , -1);
      }
   }
   return ans;
}

• 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