제출 #528634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528634		Plurm	식물 비교 (IOI20_plants)	C++11	27 / 100	460 ms	19076 KiB

plants

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

int seg[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
int lazy[1 << 19];
int sidx[1 << 19];
void build(int c, int l, int r) {
  lb[c] = l;
  rb[c] = r;
  sidx[c] = l;
  if (l == r)
    return;
  int k = (l + r) / 2;
  build(2 * c, l, k);
  build(2 * c + 1, k + 1, r);
}

void prop(int c) {
  if (lazy[c]) {
    seg[c] += lazy[c];
    if (lb[c] != rb[c]) {
      lazy[2 * c] += lazy[c];
      lazy[2 * c + 1] += lazy[c];
    }
    lazy[c] = 0;
  }
}

void update(int c, int l, int r, int x) {
  if (lb[c] == l && rb[c] == r)
    lazy[c] += x;
  prop(c);
  if (lb[c] == l && rb[c] == r)
    return;
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r) {
    update(2 * c, l, k, x);
    update(2 * c + 1, k + 1, r, x);
  } else if (r <= k) {
    update(2 * c, l, r, x);
    prop(2 * c + 1);
  } else {
    prop(2 * c);
    update(2 * c + 1, l, r, x);
  }
  if (seg[2 * c] <= seg[2 * c + 1]) {
    seg[c] = seg[2 * c];
    sidx[c] = sidx[2 * c];
  } else {
    seg[c] = seg[2 * c + 1];
    sidx[c] = sidx[2 * c + 1];
  }
}

pair<int, int> query(int c, int l, int r) {
  prop(c);
  if (lb[c] == l && rb[c] == r)
    return make_pair(seg[c], sidx[c]);
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r)
    return min(query(2 * c, l, k), query(2 * c + 1, k + 1, r));
  else if (r <= k)
    return query(2 * c, l, r);
  else
    return query(2 * c + 1, l, r);
}

vector<int> h; // recovered
void init(int k, vector<int> r) {
  int n = r.size();
  h.resize(n, 0);
  build(1, 0, n - 1);
  for (int i = 0; i < n; i++) {
    update(1, i, i, r[i]);
  }
  for (int it = 0; it < n; it++) {
    int m = query(1, 0, n - 1).second;
    if (m + k < n) {
      auto p = query(1, m + k, n - 1);
      if (p.first == 0) {
        m = p.second;
      }
    }
    // printf("DBG %d\n", m);
    h[m] = n - it;
    if (m >= k - 1) {
      update(1, m - k + 1, m - 1, -1);
    } else {
      if (m != 0)
        update(1, 0, m - 1, -1);
      update(1, m + n - k + 1, n - 1, -1);
    }
    update(1, m, m, 1e9);
  }
}

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: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25