제출 #1323671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323671		SmuggingSpun	서열 (APIO23_sequence)	C++17	100 / 100	1306 ms	66564 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 5e5 + 5;
template<class T>void minimize(T& a, T b){
  if(a > b){
    a = b;
  }
}
template<class T>void maximize(T& a, T b){
  if(a < b){
    a = b;
  }
}
int n, a[lim];
namespace sub12{
  int solve(){
    vector<int>bit(n + 1);
    function<void(int)>update = [&] (int p){
      for(; p <= n; p += p & -p){
        bit[p]++;
      }	
    };
    function<int(int)>get = [&] (int p){
      int ans = 0;
      for(; p > 0; p -= p & -p){
        ans += bit[p];
      }	
      return ans;
    };
    int ans = 0;
    for(int i = 1; i <= n; i++){
      fill(bit.begin(), bit.end(), 0);
      for(int j = i; j <= n; j++){
        update(a[j]);
        int low = 1, high = n, x = j - i + 1, median;
        while(low <= high){
          int mid = (low + high) >> 1;
          if(get(mid) >= (x >> 1) + (x & 1)){
            high = (median = mid) - 1;
          }
          else{
            low = mid + 1;
          }
        }
        maximize(ans, get(median) - get(median - 1));
        if((~x & 1) && get(median) == (x >> 1)){
          low = median + 1;
          high = n;
          while(low <= high){
            int mid = (low + high) >> 1;
            if(get(mid) > (x >> 1)){
              high = (median = mid) - 1;
            }
            else{
              low = mid + 1;
            }
          }
          maximize(ans, get(median) - get(median - 1));
        }
      }
    }
    return ans;
  }
}
namespace sub4{
  int solve(){
    vector<int>_a;
    for(int i = 1; i <= n; i++){
      _a.push_back(a[i]);
    }    
    sort(_a.begin(), _a.end());
    if(_a[n >> 1] != 2 || _a[(n - 1) >> 1] != 2){
      return count(a + 1, a + n + 1, _a[n >> 1]);
    }
    int ans = count(a + 1, a + n + 1, 2);
    vector<int>bit((n << 1) + 5, 0);
    auto update = [&] (int p, int x){
      for(p += n + 1; p < bit.size(); p += p & -p){
        minimize(bit[p], x);
      }
    };
    auto get = [&] (int p){
      int ans = n;
      for(p += n + 1; p > 0; p -= p & -p){
        minimize(ans, bit[p]);
      }
      return ans;
    };
    for(int z = 0; z < 2; z++){
      for(int i = 1; i <= n; i++){
        if(a[i] == 1 || a[i] == 3){
          a[i] ^= 2;
        }
      }
      fill(bit.begin(), bit.end(), n);
      update(0, 0);
      for(int i = 1, f = 0; i <= n; update(f, i++)){
        maximize(ans, (i - get(f += a[i] == 1 ? 1 : -1) + 1) >> 1);
      }
    }
    return ans;
  }
}
namespace sub3567{
  const int INF = 1e9;
  struct SegmentTree{
    bool get_min;
    int st[lim << 2], lazy[lim << 2];
    void build(int id, int l, int r){
      st[id] = get_min ? l : r;
      lazy[id] = 0;
      if(l < r){
        int m = (l + r) >> 1;
        build(id << 1, l, m);
        build(id << 1 | 1, m + 1, r);
      }
    }
    void init(bool get_min){
      this->get_min = get_min;
      build(1, 0, n);
    }
    void propagate(int id, int x){
      st[id] += x;
      lazy[id] += x;
    }
    void push_down(int id){
      propagate(id << 1, lazy[id]);
      propagate(id << 1 | 1, lazy[id]);
      lazy[id] = 0;
    }
    void update(int id, int l, int r, int u, int v, int x){
      if(l > v || r < u){
        return;
      }
      if(u <= l && v >= r){
        propagate(id, x);
        return;
      }
      int m = (l + r) >> 1;
      push_down(id);
      update(id << 1, l, m, u, v, x);
      update(id << 1 | 1, m + 1, r, u, v, x);
      st[id] = get_min ? min(st[id << 1], st[id << 1 | 1]) : max(st[id << 1], st[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v){
      if(l > v || r < u){
        return get_min ? INF : -INF;
      }
      if(u <= l && v >= r){
        return st[id];
      }
      push_down(id);
      int m = (l + r) >> 1, left = get(id << 1, l, m, u, v), right = get(id << 1 | 1, m + 1, r, u, v);
      return get_min ? min(left, right) : max(left, right);
    }
  };
  SegmentTree st_min_1, st_max_1, st_min_2, st_max_2;
  bool check(int l, int r){
    return ll(st_max_1.get(1, 0, n, r, n) - st_min_1.get(1, 0, n, 0, l - 1)) * (st_min_2.get(1, 0, n, r, n) - st_max_2.get(1, 0, n, 0, l - 1)) < 1;
  }
  vector<int>pos[lim];
  int solve(){
    st_min_1.init(true);
    st_max_1.init(false);
    st_min_2.init(true);
    st_max_2.init(false);
    for(int i = 1; i <= n; i++){
      pos[a[i]].push_back(i);
    }
    int ans = 0;
    for(int x = 1; x <= n; x++){
      for(int& i : pos[x]){
        st_min_2.update(1, 0, n, i, n, -2);
        st_max_2.update(1, 0, n, i, n, -2);
      }
      for(int l = 0, r = 0; l < pos[x].size(); l++){
        maximize(r, l);
        while(r < pos[x].size() && check(pos[x][l], pos[x][r])){
          r++;
        }
        maximize(ans, r - l);
      }
      for(int& i : pos[x]){
        st_min_1.update(1, 0, n, i, n, -2);
        st_max_1.update(1, 0, n, i, n, -2);
      }
    }
    return ans;
  }
}
int sequence(int _n, vector<int>_a){
  for(int i = n = _n; i > 0; i--){
    a[i] = _a[i - 1];
  }
  if(n <= 2000){
    return sub12::solve();
  }
  if(*max_element(a + 1, a + n + 1) <= 3){
    return sub4::solve();
  }
  return sub3567::solve();
}

• 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