Submission #218120

#	Time	Username	Problem	Language	Result	Execution time	Memory
218120		extraterrestrial	Candies (JOI18_candies)	C++14	100 / 100	702 ms	46328 KiB

candies

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

mt19937 rnd(239);

struct DSU {
  vector<int> p, l, r;
  DSU(int n) {
    p.resize(n + 1);
    l.resize(n + 1);
    r.resize(n + 1);
    iota(all(p), 0);
    iota(all(l), 0);
    iota(all(r), 0);
  }
  int find(int v) {
    return p[v] == v ? v : p[v] = find(p[v]);
  }
  void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) {
      return;
    }
    if (rnd() & 1) {
      swap(a, b);
    }
    p[b] = a;
    l[a] = min(l[a], l[b]);
    r[a] = max(r[a], r[b]);
  }
};

struct ST {
  vector<int> t;
  void init(int n) {
    t.resize(4 * n + 10, -1);
  }
  void push(int v) {
    if (t[v] != -1) {
      t[2 * v] = t[v];
      t[2 * v + 1] = t[v];
      t[v] = -1;
      return;
    }
  }
  void update(int v, int l, int r, int a, int b, int vl) {
    if (l > b || r < a) {
      return;
    }
    if (l >= a && r <= b) {
      t[v] = vl;
      return;
    }
    push(v);
    int mid = (l + r) / 2;
    update(2 * v, l, mid, a, b, vl);
    update(2 * v + 1, mid + 1, r, a, b, vl);
  }
  int get(int v, int l, int r, int need) {
    if (l == r) {
      return t[v];
    }
    push(v);
    int mid = (l + r) / 2;
    if (need <= mid) {
      return get(2 * v, l, mid, need);
    }
    else {
      return get(2 * v + 1, mid + 1, r, need);
    }
  }
  /*void init(int n) {
    t.resize(n + 1);
  }
  void update(int v, int l, int r, int a, int b, int vl) {
    for (int i = a; i <= b; i++) {
      t[i] = vl;
    }
  }
  int get(int v, int l, int r, int need) {
    return t[need];
  }*/
};

ST tree1, tree2;
const int N = 2e5 + 10;
int a[N], pref[N];

inline int get_sum(int l, int r) {
  int rez = pref[r] - pref[l - 1];
  if (l % 2 == 0) {
    rez *= -1;
  }
  return rez;
}

int n;

inline int check(int x) {
  if (x & 1) {
    return tree1.get(1, 1, n, x);
  }
  else {
    return tree2.get(1, 1, n, x);
  }
}

set<int> unmerged[2];

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1];
    if (i & 1) {
      pref[i] += a[i];
    }
    else {
      pref[i] -= a[i];
    }
  }
  for (int i = 1; i + 2 <= n; i++) {
    unmerged[i % 2].insert(i);
  }
  tree1.init(n);
  tree2.init(n);
  DSU kek(n);
  tree1.update(1, 1, n, 1, n, 0);
  tree2.update(1, 1, n, 1, n, 0);
  set<pair<int, int>> can;
  for (int i = 1; i <= n; i++) {
    can.insert({a[i], i});
  }	
  set<pair<int, pair<int, int>>> can_flip;
  int all = 0;
  for (int i = 1; i <= (n + 1) / 2; i++) {
    pair<int, int> mx = {-1e18, 0};
    if (!can.empty()) {
      mx = *(--can.end());
    }
    pair<int, pair<int, int>> mx2 = {-1e18, {0, 0}};
    if (!can_flip.empty()) {
      mx2 = *(--can_flip.end());
    }
    if (mx.F > mx2.F) {
      all += mx.F;
      can.erase(--can.end());
      //cout << 1 << ' ' << mx.S << '\n';
      if (mx.S > 1 && can.find({a[mx.S - 1], mx.S - 1}) != can.end()) {
        can.erase({a[mx.S - 1], mx.S - 1});
      }
      if (mx.S < n && can.find({a[mx.S + 1], mx.S + 1}) != can.end()) {
        can.erase({a[mx.S + 1], mx.S + 1});
      }
      if (mx.S & 1) {
        tree1.update(1, 1, n, mx.S, mx.S, 1);
      }
      else {
        tree2.update(1, 1, n, mx.S, mx.S, 1);
      }

      if (mx.S > 2 && check(mx.S - 2)) {
        int comp = kek.find(mx.S - 2);
        if (kek.l[comp] > 1 && kek.r[comp] < n) {
          can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
        }
        unmerged[mx.S % 2].erase(mx.S - 2);
        kek.merge(mx.S, mx.S - 2);
      }
      if (mx.S + 2 <= n && check(mx.S + 2)) {
        int comp = kek.find(mx.S + 2);
        if (kek.l[comp] > 1 && kek.r[comp] < n) {
          can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
        }
        unmerged[mx.S % 2].erase(mx.S);
        kek.merge(mx.S, mx.S + 2);
      }
      int comp = kek.find(mx.S);
      if (kek.l[comp] > 1 && kek.r[comp] < n) {
        can_flip.insert(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
      }
    }
    else {
      //cout << i << ' ' << 2 << '\n';
      all += mx2.F;
      int L = mx2.S.F, R = mx2.S.S;
      //cout << L << ' ' << R << '\n';
      if (L > 2 && can.find({a[L - 2], L - 2}) != can.end()) {
        can.erase({a[L - 2], L - 2});
      }
      if (R + 2 <= n && can.find({a[R + 2], R + 2}) != can.end()) {
        can.erase({a[R + 2], R + 2});
      }
      if (L & 1) {
        tree1.update(1, 1, n, L, R, 0);
        tree2.update(1, 1, n, L - 1, R + 1, 1);
      } 
      else {
        tree2.update(1, 1, n, L, R, 0);
        tree1.update(1, 1, n, L - 1, R + 1, 1);
      }
      can_flip.erase(--can_flip.end());
      L--, R++;
      for (;;) {
        auto it = unmerged[L % 2].lower_bound(L);
        if (it == unmerged[L % 2].end() || *it > R - 2) {
          break;
        }
        kek.merge(*it, *it + 2);
        unmerged[L % 2].erase(it);
        //cout << "C " << *it << '\n';
      }
      if (L > 2 && check(L - 2)) {
        int comp = kek.find(L - 2);
        if (kek.l[comp] > 1 && kek.r[comp] < n) {
          can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
        }
        unmerged[L % 2].erase(L - 2);
        kek.merge(L, L - 2);
      }
      if (R + 2 <= n && check(R + 2)) {
        int comp = kek.find(R + 2);
        if (kek.l[comp] > 1 && kek.r[comp] < n) {
          can_flip.erase(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
        }
        unmerged[R % 2].erase(R);
        kek.merge(R, R + 2);
      }
      int comp = kek.find(L);
      if (kek.l[comp] > 1 && kek.r[comp] < n) {
        can_flip.insert(make_pair(get_sum(kek.l[comp] - 1, kek.r[comp] + 1), make_pair(kek.l[comp], kek.r[comp])));
      } 
    }
    cout << all << '\n';
    /*for (int i = 1; i <= n; i++) {
      cout << check(i) << ' ';
    }
    cout << '\n';*/
  }
} 

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92