Submission #1131425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131425		duckindog	Sequence (APIO23_sequence)	C++17	60 / 100	774 ms	64344 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "sequence.h"
#endif

const int N = 500'000 + 10;
int n;
int a[N];
vector<int> pos[N];

namespace IT { 
  struct Node { 
    int mi, ma;
    Node() : mi(1'000'000), ma(-1'000'000) {}
    Node(int mi, int ma) : mi(mi), ma(ma) {} 
  } f[N << 2];
  int lazy[N << 2];
  
  inline Node merge(const Node& lt, const Node& rt) { 
    return Node(min(lt.mi, rt.mi), max(lt.ma, rt.ma));
  }

  void build(int s, int l, int r) { 
    f[s] = Node(0, 0);
    lazy[s] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
  }

  void push(int s) { 
    if (!lazy[s]) return;
    f[s << 1].mi += lazy[s];  f[s << 1 | 1].mi += lazy[s];
    f[s << 1].ma += lazy[s];  f[s << 1 | 1].ma += lazy[s];
    lazy[s << 1] += lazy[s];  lazy[s << 1 | 1] += lazy[s];
    lazy[s] = 0;
  }
  void update(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      f[s].mi += x;
      f[s].ma += x;
      lazy[s] += x;
      return;
    }
    push(s);
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
    f[s] = merge(f[s << 1], f[s << 1 | 1]);
  }
  Node query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return Node();
    if (u <= l && r <= v) return f[s];
    int mid = (l + r) >> 1;
    return merge(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
  }
}
IT::Node saveL[N], saveR[N];

int sequence(int inN, std::vector<int> inA) {
  { // input
    n = inN;
    for (int i = 1; i <= n; ++i) a[i] = inA[i - 1];
  }
  for (int i = 1; i <= n; ++i) pos[i] = {0};
  for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i);

  { // init save array
    IT::build(1, 1, n);
    for (int i = 1; i <= n; ++i) 
      IT::update(1, 1, n, i, n, 1);

    saveL[0] = {0, 0};    
    for (int index = 1; index <= n; ++index) { 
      for (int i = 1; i < (int)pos[index].size(); ++i) 
        IT::update(1, 1, n, pos[index][i], n, -1);

      for (int i = 1; i < (int)pos[index].size(); ++i) { 
        int p = pos[index][i];
        saveL[p - 1] = IT::merge(saveL[0], IT::query(1, 1, n, 1, p - 1));
        saveR[p] = IT::query(1, 1, n, p, n);
      }

      for (int i = 1; i < (int)pos[index].size(); ++i) 
        IT::update(1, 1, n, pos[index][i], n, -1);
    }
  }

  auto chk = [&](int length) { 
    for (int index = 1; index <= n; ++index) { 
      for (int i = 1; i <= (int)pos[index].size() - length; ++i) { 
        int l = pos[index][i], r = pos[index][i + length - 1];
        if (max(saveL[l - 1].mi, saveR[r].mi) - 
            min(saveL[l - 1].ma, saveR[r].ma) <= length) return true;
      }
    }
    return false;
  };

  int le = 1, ri = n, answer = 1;
  while (le <= ri) { 
    int mid = (le + ri) >> 1;
    if (chk(mid)) le = (answer = mid) + 1;
    else ri = mid - 1;
  }
  
  return answer;
}

#ifdef LOCAL
int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  printf("%d\n", result);
  return 0;
}
#endif

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