Submission #1018181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018181		TAhmed33	Sequence (APIO23_sequence)	C++17	100 / 100	1815 ms	110784 KiB

sequence

#include "sequence.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node << 1)
#define tr (tl | 1)
int n;
struct SegmenTree {
  int mn[MAXN << 2], mx[MAXN << 2], lazy[MAXN << 2];
  void prop (int l, int r, int node) {
    if (lazy[node] == 0) return;
    if (l != r) {
      lazy[tl] += lazy[node];
      lazy[tr] += lazy[node];
    }
    mx[node] += lazy[node];
    mn[node] += lazy[node];
    lazy[node] = 0;
  }
  void pull (int l, int r, int node) {
    mn[node] = min(mn[tl], mn[tr]);
    mx[node] = max(mx[tl], mx[tr]);
  }
  void add (int l, int r, int a, int b, int c, int node) {
    prop(l, r, node);
    if (l > b || r < a) return;
    if (l >= a && r <= b) {
      lazy[node] += c;
      prop(l, r, node);
      return;
    }
    add(l, mid, a, b, c, tl);
    add(mid + 1, r, a, b, c, tr);
    pull(l, r, node);
  }
  int get_mx (int l, int r, int a, int b, int node) {
    prop(l, r, node);
    if (l > b || r < a) return -1e9;
    if (l >= a && r <= b) return mx[node];
    return max(get_mx(l, mid, a, b, tl), get_mx(mid + 1, r, a, b, tr));
  }
  int get_mn (int l, int r, int a, int b, int node) {
    prop(l, r, node);
    if (l > b || r < a) return 1e9;
    if (l >= a && r <= b) return mn[node];
    return min(get_mn(l, mid, a, b, tl), get_mn(mid + 1, r, a, b, tr));
  }
} cur;
struct ImplicitSegmentTree {
  vector <int> tree, lc, rc;
  int cnt = 0;
  void new_node () {
    cnt++; tree.push_back(MAXN); lc.push_back(-1); rc.push_back(-1);
  }
  void init () {
    tree.clear(); lc.clear(); rc.clear(); cnt = 0;
    new_node();
  }
  void pull (int node) {
    if (lc[node] != -1) tree[node] = min(tree[node], tree[lc[node]]);
    if (rc[node] != -1) tree[node] = min(tree[node], tree[rc[node]]);
  }
  void update (int l, int r, int a, int b, int node) {
    if (l > a || r < a) return;
    if (l == r) {
      tree[node] = min(tree[node], b);
      return;
    }
    if (a <= mid) {
      if (lc[node] == -1) {
        new_node(); lc[node] = cnt - 1;
      }
      update(l, mid, a, b, lc[node]);
    } else {
      if (rc[node] == -1) {
        new_node(); rc[node] = cnt - 1;
      }
      update(mid + 1, r, a, b, rc[node]);
    }
    pull(node);
  }
  int get (int l, int r, int a, int b, int node) {
    if (l > b || r < a) return MAXN;
    if (l >= a && r <= b) return tree[node];
    int mn = MAXN;
    if (lc[node] != -1) {
      mn = min(mn, get(l, mid, a, b, lc[node]));
    }
    if (rc[node] != -1) {
      mn = min(mn, get(mid + 1, r, a, b, rc[node]));
    }
    return mn;
  }
} dd;
int solve1 (vector <pair <int, int>> b) {
  int mx = 0;
  vector <array <int, 4>> events;
  for (int i = 0; i < int(b.size()); i++) {
    events.push_back({b[i].second, b[i].first, 1, i});
    events.push_back({b[i].first, b[i].second, 0, i});
  }
  sort(events.begin(), events.end(), [&] (array <int, 4> x, array <int, 4> y) {
    if (x[0] == y[0] && x[1] == y[1]) return x[2] < y[2];
    if (x[0] == y[0]) return x[1] > y[1];
    return x[0] < y[0];
  });
  dd.init();
  for (int i = 0; i < int(events.size()); i++) {
    if (events[i][2] == 0) {
      dd.update(0, 4 * n, 2 * n + events[i][1], events[i][3], 0);
    } else {
      mx = max(mx, events[i][3] - dd.get(0, 4 * n, 2 * n + events[i][1], 4 * n, 0));
    }
  }
  return mx;
}
int solve2 (vector <pair <int, int>> b) {
  int mx = 0;
  vector <array <int, 4>> events;
  for (int i = 0; i < int(b.size()); i++) {
    events.push_back({b[i].second, b[i].second + i, 1, i});
    events.push_back({b[i].first, b[i].first + i, 0, i});
  }
  sort(events.begin(), events.end());
  reverse(events.begin(), events.end());
  dd.init();
  for (int i = 0; i < int(events.size()); i++) {
    int j = i;
    while (j + 1 < int(events.size()) && events[j + 1][0] == events[i][0]) {
      j++;
    }
    for (int k = i; k <= j; k++) {
      if (events[k][2] == 1) {
        mx = max(mx, events[k][3] - dd.get(0, 4 * n, 0, 2 * n + events[k][1], 0));
      }
    }
    for (int k = i; k <= j; k++) {
      if (events[k][2] == 0) {
        dd.update(0, 4 * n, 2 * n + events[k][1], events[k][3], 0);
      }
    }
    i = j;
  }
  return mx;
}
int solve3 (vector <pair <int, int>> b) {
  int mx = 0;
  vector <array <int, 4>> events;
  for (int i = 0; i < int(b.size()); i++) {
    events.push_back({b[i].first, b[i].first - i, 1, i});
    events.push_back({b[i].second, b[i].second - i, 0, i});
  }
  sort(events.begin(), events.end());
  dd.init();
  for (int i = 0; i < int(events.size()); i++) {
    int j = i;
    while (j + 1 < int(events.size()) && events[j + 1][0] == events[i][0]) {
      j++;
    }
    for (int k = i; k <= j; k++) {
      if (events[k][2] == 1) {
        mx = max(mx, events[k][3] - dd.get(0, 4 * n, 2 * n + events[k][1], 4 * n, 0));
      }
    }
    for (int k = i; k <= j; k++) {
      if (events[k][2] == 0) {
        dd.update(0, 4 * n, 2 * n + events[k][1], events[k][3], 0);
      }
    }
    i = j;
  }
  return mx;
}
int a[MAXN];
vector <int> occ[MAXN];
int sequence (int NB, vector <int> AB) {
  n = NB;
  for (int i = 1; i <= n; i++) {
    occ[i].push_back(0);
  }
  for (int i = 1; i <= n; i++) {
    a[i] = AB[i - 1];
    occ[a[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    occ[i].push_back(n + 1);
  }
  for (int i = 1; i <= n; i++) {
    cur.add(0, n, i, i, i, 1);
  }
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    for (auto j : occ[i - 1]) {
      cur.add(0, n, j, n, -1, 1);
    }
    for (auto j : occ[i]) {
      cur.add(0, n, j, n, -1, 1);
    }
    vector <pair <int, int>> b;
    for (int j = 0; j + 1 < int(occ[i].size()); j++) {
      b.push_back({cur.get_mn(0, n, occ[i][j], occ[i][j + 1] - 1, 1), cur.get_mx(0, n, occ[i][j], occ[i][j + 1] - 1, 1)});
    }
    mx = max(mx, solve1(b));
    mx = max(mx, solve2(b));
    mx = max(mx, solve3(b));
  }
  return mx;
}

• 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