제출 #301923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
301923		rama_pang	식물 비교 (IOI20_plants)	C++14	44 / 100	1909 ms	18604 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;

// 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);

  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);
    }
  }
}

int compare_plants(int x, int y) {
  return h[x] > h[y] ? 1 : -1;
}

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