Submission #390511

#	Time	Username	Problem	Language	Result	Execution time	Memory
390511		AlexPop28	Comparing Plants (IOI20_plants)	C++11	44 / 100	547 ms	39304 KiB

plants

#include "plants.h"
#include <cassert>
#include <iostream>
// regret ca mi a fost lene sa scriu 2 linii de define uri si am stat sa scriu printf uri ca prostu

using namespace std;

struct SegmTree {
  int n;
  vector<int> lazy;
  vector<pair<int, int>> t;
  SegmTree() {}
  SegmTree(const vector<int> &r) : n(r.size()) {
    int sz = 1; while (sz < n) sz *= 2;
    lazy.resize(2 * sz);
    t.resize(2 * sz);
    Build(0, 0, n - 1, r);
  }

  void Build(int node, int left, int right, const vector<int> &r) {
    if (left == right) {
      t[node] = {r[left], left};
      return;
    }
    int mid = (left + right) / 2;
    Build(2 * node + 1, left, mid, r);
    Build(2 * node + 2, mid + 1, right, r);
    t[node] = max(t[2 * node + 1], t[2 * node + 2]);
  }

  void Push(int node) {
    if (lazy[node] == 0) return;
    for (int son : {2 * node + 1, 2 * node + 2}) {
      t[son].first += lazy[node];
      lazy[son] += lazy[node];
    }
    lazy[node] = 0;
  }

  pair<int, int> Max(int node, int left, int right, int x, int y) {
    if (x <= left && right <= y) {
      return t[node];
    }

    Push(node);
    int mid = (left + right) / 2;
    if (y <= mid)
      return Max(2 * node + 1, left, mid, x, y);
    if (mid < x)
      return Max(2 * node + 2, mid + 1, right, x, y);
    return max(
      Max(2 * node + 1, left, mid, x, y),
      Max(2 * node + 2, mid + 1, right, x, y)
    );
  }

  void Add(int node, int left, int right, int x, int y, int val) {
    // printf("node = %d, left = %d, right = %d\n", node, left, right);
    // printf("x = %d, y = %d\n", x, y);
    // printf("%d\n", x <= left && right <= y);
    if (x <= left && right <= y) {
      t[node].first += val;
      lazy[node] += val;
      // printf("left = %d, val = %d\n", left, val);
      return;
    }
    
    Push(node);
    int mid = (left + right) / 2;
    if (x <= mid)
      Add(2 * node + 1, left, mid, x, y, val);
    if (mid < y)
      Add(2 * node + 2, mid + 1, right, x, y, val);
    t[node] = max(t[2 * node + 1], t[2 * node + 2]);
  }

  pair<int, int> Max(int l, int r) {
    if (l >= 0) {
      return Max(0, 0, n - 1, l, r);
    }
    l += n;
    if (r >= 0)
      return max(Max(0, r), Max(l, n - 1));
    return Max(l, r + n);
  }

  void Add(int l, int r, int val) {
    // printf("l = %d, r = %d, val = %d\n", l, r, val);
    // printf("n = %d\n", n);
    if (l >= 0) {
      Add(0, 0, n - 1, l, r, val);
      return;
    }
    l += n;
    if (r >= 0) {
      Add(0, 0, n - 1, 0, r, val);
      Add(0, 0, n - 1, l, n - 1, val);
      return;
    }
    Add(0, 0, n - 1, l, r + n, val);
  }
};

int n, k;
int curr_h = 0;
vector<int> h;
SegmTree st;

void SetH(int pos) {
  pair<int, int> p;
  while ((p = st.Max(pos - k + 1, pos - 1)).first == k - 1) {
    SetH(p.second);
  }

  h[pos] = ++curr_h;
  // printf("pos = %d\n", pos);
  st.Add(pos - k + 1, pos - 1, +1);
  st.Add(pos, pos, -n);
  // printf("(%d, %d)\n", st.Max(pos - k + 1, pos - 1).first, st.Max(pos - k + 1, pos - 1).second);
}

void init(int k_, vector<int> r) {
  n = r.size();
  k = k_;
  st = SegmTree(r);
  h.resize(n);

  pair<int, int> p;
  while ((p = st.Max(0, n - 1)).first == k - 1) {
    // printf("pp = %d\n", p.second);
    // printf("val = %d\n", p.first);
    SetH(p.second);
  }
  // printf("p = (%d, %d)\n", p.first, p.second);
}

int compare_plants(int x, int y) {
  return 2 * (h[x] > h[y]) - 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