Submission #827579

#	Time	Username	Problem	Language	Result	Execution time	Memory
827579		erray	Comparing Plants (IOI20_plants)	C++17	0 / 100	1 ms	428 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/day2/debug.h"
#else 
  #define debug(...) void(37)
#endif

const int inf = int(1e9);
struct SegTree {
  struct node {
    array<int, 2> mn{}; 
    int tag = 0;
    node operator+(node x) {
      node res;
      res.mn = min(mn, x.mn);
      return res;
    }
    void modify(int x) {
      tag += x;
      mn[0] += x;
    }
  };
  vector<node> tree;
  int n;
  void push(int v, int rv) {
    tree[v + 1].modify(tree[v].tag);
    tree[rv].modify(tree[v].tag);
    tree[v].tag = 0;
  }
  #define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
  void modify(int v, int l, int r, int ll, int rr, int x) {
    debug(v, l, r, ll, rr, x);
    if (l >= ll && rr >= r) {
      if (l == r) {
        tree[v].mn[1] = l;
      }
      tree[v].modify(x);
      debug(v, l, r, tree[v].mn);
      return;
    }
    def;
    push(v, rv);
    if (mid >= ll) {
      modify(v + 1, l, mid, ll, rr, x);
    }
    if (mid < rr) {
      modify(rv, mid + 1, r, ll, rr, x);
    }
    tree[v] = tree[v + 1] + tree[rv];
    debug(v, l, r, tree[v].mn);
  }
  array<int, 2> root() {
    return tree[0].mn;
  }
  void modify(int l, int r, int x) {
    modify(0, 0, n - 1, l, r, x);
  }
  SegTree(int _n) : n(_n) {
    tree.resize(n * 2);
  }
};

int N, K, LG;
vector<int> ord;
vector<vector<int>> liftL, liftR;

void init(int _K, std::vector<int> R) {
  N = int(R.size());
  K = _K;
  LG = __lg(N) + 1;
  SegTree st(N);
  for (int i = 0; i < N; ++i) {
    st.modify(i, i, +R[i]);
  }
  debug(N, K, LG, R);
  set<int> act;
  set<pair<int, int>> dists;
  vector<int> cur_len(N, -1);
  vector<int> use;
  auto Upd_len = [&](int x) {
    debug("upd after", x);
    if (act.empty()) {
      return;
    }
    auto it = act.lower_bound(x);
    if (it == act.begin()) {
      it = act.end();
    }
    it = prev(it);
    x = *it;
    debug("upd", x);
    //debug(dists);
    if (cur_len[x] != -1) {
      dists.erase(dists.find(pair{cur_len[x], x}));
    }
    it = next(it);
    if (it == act.end()) {
      int from = *act.begin();
      cur_len[x] = from + N - x;
    } else {
      cur_len[x] = *it - x;
    }
    dists.emplace(cur_len[x], x);
  };
  auto Add_seg = [&](int x) {    
    debug("add", x);
    act.insert(x);
    Upd_len(x + 1);
    Upd_len(x);
  };
  vector<int> next(N, -1);
  auto Push_segs = [&](int last) {
    debug(st.root());
    while (st.root()[0] == 0) {
      debug("add", st.root());
      int id = st.root()[1];
      st.modify(id, id, +inf);
      next[id] = (last == -1 ? id : last);
      Add_seg(id);
    }
  };
  Push_segs(-1);
  ord.resize(N);
  for (int i = 0; i < N; ++i) {
    debug(dists);
    assert(!dists.empty());
    auto it = prev(dists.end());
    auto[len, id] = *it;
    debug("########################", i, len, id);
    ord[id] = i;
    assert(len >= K);
    dists.erase(it);
    act.erase(id);
    Upd_len(id);
    int r = id + K - 1;
    debug("upd seg tree");
    if (r < N) {
      debug(id, r);
      st.modify(id, r, -1);
    } else {
      debug(id, N - 1);
      debug(0, r);
      r %= N;
      st.modify(id, N - 1, -1);
      st.modify(0, r, -1);
    }
    Push_segs(id);
  }
  liftL.resize(LG, vector<int>(N));
  liftR.resize(LG, vector<int>(N));
  set<pair<int, int>> mx;
  for (int i = 1; i < K; ++i) {
    mx.emplace(ord[i], i);
  }
  for (int i = 0; i < N; ++i) {
    auto it = mx.lower_bound(pair{ord[i], -1});
    liftR[0][i] = (it == mx.begin() ? i : prev(it)->second);
    int add = (i + K) % N;
    mx.emplace(ord[add], add);
    int rem = (i + 1) % N;
    mx.erase(pair{ord[rem], rem});
  }
  liftL[0] = next;
  for (int l = 1; l < LG; ++l) {
    for (int i = 0; i < N; ++i) {
      liftL[l][i] = liftL[l - 1][liftL[l - 1][i]]; 
      liftR[l][i] = liftR[l - 1][liftR[l - 1][i]];
    }
  }
  debug(ord, next, liftR[0]);
}

bool DependsL(int x, int y) {
  if (ord[x] > ord[y]) {
    swap(x, y);
  }
  debug(x, y);
  auto Between = [&](int go) {
    return (x <= y ? (x < go && go <= y) : (go <= y || x < go));
  };
  for (int l = LG - 1; l >= 0; --l) {
    int go = liftL[l][y];
    if (Between(go)) {
      swap(go, y);
    }
  }
  debug(x, y);
  y = liftL[0][y];
  debug(y);
  return !Between(y) || y == x; //replace with movability check if it gets wa
}

bool DependsR(int x, int y) {
  if (ord[x] > ord[y]) {
    swap(x, y);
  }
  debug(x, y);
  auto Between = [&](int go) {
    return (x >= y ? (x > go && go >= y) : (go >= y || x > go));
  };
  for (int l = LG - 1; l >= 0; --l) {
    int go = liftR[l][y];
    debug(go, Between(go));
    if (Between(go)) {
      swap(go, y);
    }
  }
  y = liftR[0][y];
  return !Between(y) || y == x; //replace with movability check if it gets wa
}

#define SUBTASK3 true

int compare_plants(int x, int y) {
  debug("compare", x, y);
	if (SUBTASK3 || DependsL(x, y) || DependsR(x, y)) {
    return (ord[x] < ord[y] ? 1 : -1);
  }
  return 0;
  
}

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