Submission #301945

#	Time	Username	Problem	Language	Result	Execution time	Memory
301945		rama_pang	Comparing Plants (IOI20_plants)	C++14	100 / 100	3353 ms	79332 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

class PotentialMaximum {
 public:
  PotentialMaximum() {}
  PotentialMaximum(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
    Build(1, 0, n - 1, r);
  }

  void UpdateIndeg(int x, int z = 1) {
    int l = x + 1;
    int r = x + k - 1;
    while (l >= n) {
      l -= n;
      r -= n;
    }
    if (n <= r) {
      Update(1, 0, n - 1, l, n - 1, 0, z);
      Update(1, 0, n - 1, 0, r - n, 0, z);
    } else {
      Update(1, 0, n - 1, l, r, 0, z);
    }
  }

  void UpdateRank(int x, int z) {
    int l = x - k + 1;
    int r = x - 1;
    while (l < 0) {
      l += n, r += n;
    }
    if (n <= r) {
      Update(1, 0, n - 1, l, n - 1, z, 0);
      Update(1, 0, n - 1, 0, r - n, z, 0);
    } else {
      Update(1, 0, n - 1, l, r, z, 0);
    }
  }

  void Delete(int x) {
    UpdateRank(x, -1);
    UpdateIndeg(x, -1);
    Update(1, 0, n - 1, x, x, 1e9, 1e9);
  }

  int Query() {
    return tree[1].id;
  }

 private:
  struct Node {
    int id;
    int rank;
    int indeg;
    int lazyrank;
    int lazyindeg;
  };

  int n, k;
  vector<Node> tree;

  void Apply(int u, int r, int d) {
    tree[u].rank += r;
    tree[u].lazyrank += r;
    tree[u].indeg += d;
    tree[u].lazyindeg += d;
  }

  void Push(int u, int lc, int rc) {
    Apply(lc, tree[u].lazyrank, tree[u].lazyindeg);
    Apply(rc, tree[u].lazyrank, tree[u].lazyindeg);
    tree[u].lazyrank = 0;
    tree[u].lazyindeg = 0;
  }

  void Pull(int u, int lc, int rc) {
    if (tree[lc].rank != tree[rc].rank) {
      if (tree[lc].rank < tree[rc].rank) {
        tree[u] = tree[lc];
      } else {
        tree[u] = tree[rc];
      }
    } else {
      if (tree[lc].indeg < tree[rc].indeg) {
        tree[u] = tree[lc];
      } else {
        tree[u] = tree[rc];
      }
    }
    tree[u].lazyrank = 0;
    tree[u].lazyindeg = 0;
  }

  void Build(int u, int tl, int tr, const vector<int> &r) {
    if (tl == tr) {
      tree[u].id = tl;
      tree[u].rank = r[tl];
      tree[u].indeg = 0;
      tree[u].lazyrank = 0;
      tree[u].lazyindeg = 0;
      return;
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Build(lc, tl, md, r);
    Build(rc, md + 1, tr, r);
    Pull(u, lc, rc);
  }

  void Update(int u, int tl, int tr, int l, int r, int rank, int indeg) {
    if (l > tr || tl > r || tl > tr || l > r) {
      return;
    }
    if (l <= tl && tr <= r) {
      return Apply(u, rank, indeg);
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Push(u, lc, rc);
    Update(lc, tl, md, l, r, rank, indeg);
    Update(rc, md + 1, tr, l, r, rank, indeg);
    Pull(u, lc, rc);    
  }
};

class Relax {
 public:
  Relax() {}
  Relax(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
    Build(1, 0, n - 1, r);
  }

  void Update(int x) {
    int l = x - k + 1;
    int r = x - 1;
    while (l < 0) {
      l += n, r += n;
    }
    if (n <= r) {
      Update(1, 0, n - 1, l, n - 1, -1);
      Update(1, 0, n - 1, 0, r - n, -1);
    } else {
      Update(1, 0, n - 1, l, r, -1);
    }
  }

  void Delete(int x) {
    Update(1, 0, n - 1, x, x, 1e9);
  }

  pair<int, int> Query(int x) {
    int l = x - k + 1;
    int r = x - 1;
    while (l < 0) {
      l += n, r += n;
    }
    Node res;
    if (n <= r) {
      auto ll = Query(1, 0, n - 1, l, n - 1);
      auto rr = Query(1, 0, n - 1, 0, r - n);
      if (ll.rank < rr.rank) {
        res = ll;
      } else {
        res = rr;
      }
    } else {
      res = Query(1, 0, n - 1, l, r);
    }
    return {res.id, res.rank};
  }

 private:
  struct Node {
    int id;
    int rank;
    int lazyrank;
  };

  int n, k;
  vector<Node> tree;

  void Apply(int u, int r) {
    tree[u].rank += r;
    tree[u].lazyrank += r;
  }

  void Push(int u, int lc, int rc) {
    Apply(lc, tree[u].lazyrank);
    Apply(rc, tree[u].lazyrank);
    tree[u].lazyrank = 0;
  }

  void Pull(int u, int lc, int rc) {
    if (tree[lc].rank < tree[rc].rank) {
      tree[u] = tree[lc];
    } else {
      tree[u] = tree[rc];
    }
    tree[u].lazyrank = 0;
  }

  void Build(int u, int tl, int tr, const vector<int> &r) {
    if (tl == tr) {
      tree[u].id = tl;
      tree[u].rank = r[tl];
      tree[u].lazyrank = 0;
      return;
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Build(lc, tl, md, r);
    Build(rc, md + 1, tr, r);
    Pull(u, lc, rc);
  }

  void Update(int u, int tl, int tr, int l, int r, int rank) {
    if (l > tr || tl > r || tl > tr || l > r) {
      return;
    }
    if (l <= tl && tr <= r) {
      return Apply(u, rank);
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Push(u, lc, rc);
    Update(lc, tl, md, l, r, rank);
    Update(rc, md + 1, tr, l, r, rank);
    Pull(u, lc, rc);
  }

  Node Query(int u, int tl, int tr, int l, int r) {
    if (l > tr || tl > r || tl > tr || l > r) {
      return Node({-1, (int) 1e9, (int) 1e9});
    }
    if (l <= tl && tr <= r) {
      return tree[u];
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Push(u, lc, rc);
    auto ll = Query(lc, tl, md, l, r);
    auto rr = Query(rc, md + 1, tr, l, r);
    if (ll.rank < rr.rank) {
      return ll;
    } else {
      return rr;
    }
  }
};

int n, k;
vector<int> h;
vector<vector<int>> next_inc;
vector<vector<int>> next_dec;

// Greedily find a valid arrangement h
// Indices i, j are comparable if |i - j| < k
// x and y are comparable if there exists a sequence
// h[x] < h[i1] < h[i2] < ... < h[y] and adjacent elements
// have distance < k.

void init(int k, vector<int> r) {
  n = (int) r.size();
  ::k = k;
  h.assign(n, -1);

  { // find a valid configuration h
    Relax relax(n, k, r);
    PotentialMaximum maxim(n, k, r);

    for (int i = 0; i < n; i++) {
      if (r[i] == 0) {
        relax.Delete(i);
        maxim.UpdateIndeg(i);
      }
    }

    for (int v = n - 1; v >= 0; v--) {
      int id = maxim.Query();
      h[id] = v;
      relax.Update(id);
      maxim.Delete(id);
      while (relax.Query(id).second == 0) {
        int p = relax.Query(id).first;
        maxim.UpdateIndeg(p);
        relax.Delete(p);
      }
    }
  }
  for (auto i : h) cerr << i << " "; cerr << "\n";
  { // initialize binary lifting
    for (int i = 0; i < n; i++) {
      h.emplace_back(h[i]);
    }

    set<pair<int, int>> st;
    next_inc.assign(20, vector<int>(2 * n, -1));
    next_dec.assign(20, vector<int>(2 * n, -1));

    for (int i = 2 * n - 1; i >= 0; i--) {
      if (i + k < 2 * n) {
        st.erase({h[i + k], i + k});
      }
      auto it = st.lower_bound({h[i], i});
      next_inc[0][i] = it == end(st) ? -1 : it->second;
      next_dec[0][i] = it == begin(st) ? -1 : prev(it)->second;
      st.insert({h[i], i});
    }

    for (int j = 1; j < 20; j++) {
      for (int i = 0; i < 2 * n; i++) {
        if (next_inc[j - 1][i] == -1) {
          next_inc[j][i] = -1;
        } else {
          next_inc[j][i] = next_inc[j - 1][next_inc[j - 1][i]];
        }
        if (next_dec[j - 1][i] == -1) {
          next_dec[j][i] = -1;
        } else {
          next_dec[j][i] = next_dec[j - 1][next_dec[j - 1][i]];
        }
      }
    }
  }
}

bool Sequence(int t, int x, int y) { // 0 = increasing, 1 = decreasing
  auto &nxt = (t == 0 ? next_inc : next_dec);
  for (int j = 19; j >= 0; j--) {
    if (nxt[j][x] != -1 && y - nxt[j][x] >= k) {
      x = nxt[j][x];
    }
  }
  x = nxt[0][x];
  return x != -1 && y - x < k && (t == 0 ? h[x] <= h[y] : h[x] >= h[y]);
}

int compare_plants(int x, int y) {
  bool comparable = (y - x < k);
  if (h[x] < h[y]) {
    comparable |= Sequence(0, x, y);
    comparable |= Sequence(1, y, x + n);
  } else {
    comparable |= Sequence(0, y, x + n);
    comparable |= Sequence(1, x, y);
  }
  return comparable ? (h[x] > h[y] ? 1 : -1) : 0;
}

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:296:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  296 |   for (auto i : h) cerr << i << " "; cerr << "\n";
      |   ^~~
plants.cpp:296:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  296 |   for (auto i : h) cerr << i << " "; cerr << "\n";
      |                                      ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25