Submission #528637

#	Time	Username	Problem	Language	Result	Execution time	Memory
528637		Plurm	Comparing Plants (IOI20_plants)	C++11	27 / 100	678 ms	23452 KiB

plants

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

int segmin[1 << 19];
int segmax[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
int lazymin[1 << 19];
int lazymax[1 << 19];
int sminidx[1 << 19];
int smaxidx[1 << 19];
void build(int c, int l, int r) {
  lb[c] = l;
  rb[c] = r;
  sminidx[c] = l;
  smaxidx[c] = l;
  if (l == r)
    return;
  int k = (l + r) / 2;
  build(2 * c, l, k);
  build(2 * c + 1, k + 1, r);
}

void propmin(int c) {
  if (lazymin[c]) {
    segmin[c] += lazymin[c];
    if (lb[c] != rb[c]) {
      lazymin[2 * c] += lazymin[c];
      lazymin[2 * c + 1] += lazymin[c];
    }
    lazymin[c] = 0;
  }
}

void propmax(int c) {
  if (lazymax[c]) {
    segmax[c] += lazymax[c];
    if (lb[c] != rb[c]) {
      lazymax[2 * c] += lazymax[c];
      lazymax[2 * c + 1] += lazymax[c];
    }
    lazymax[c] = 0;
  }
}

void updatemin(int c, int l, int r, int x) {
  if (lb[c] == l && rb[c] == r)
    lazymin[c] += x;
  propmin(c);
  if (lb[c] == l && rb[c] == r)
    return;
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r) {
    updatemin(2 * c, l, k, x);
    updatemin(2 * c + 1, k + 1, r, x);
  } else if (r <= k) {
    updatemin(2 * c, l, r, x);
    propmin(2 * c + 1);
  } else {
    propmin(2 * c);
    updatemin(2 * c + 1, l, r, x);
  }
  if (segmin[2 * c] <= segmin[2 * c + 1]) {
    segmin[c] = segmin[2 * c];
    sminidx[c] = sminidx[2 * c];
  } else {
    segmin[c] = segmin[2 * c + 1];
    sminidx[c] = sminidx[2 * c + 1];
  }
}

void updatemax(int c, int l, int r, int x) {
  if (lb[c] == l && rb[c] == r)
    lazymax[c] += x;
  propmax(c);
  if (lb[c] == l && rb[c] == r)
    return;
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r) {
    updatemax(2 * c, l, k, x);
    updatemax(2 * c + 1, k + 1, r, x);
  } else if (r <= k) {
    updatemax(2 * c, l, r, x);
    propmax(2 * c + 1);
  } else {
    propmax(2 * c);
    updatemax(2 * c + 1, l, r, x);
  }
  if (segmax[2 * c] >= segmax[2 * c + 1]) {
    segmax[c] = segmax[2 * c];
    smaxidx[c] = smaxidx[2 * c];
  } else {
    segmax[c] = segmax[2 * c + 1];
    smaxidx[c] = smaxidx[2 * c + 1];
  }
}

pair<int, int> querymin(int c, int l, int r) {
  propmin(c);
  if (lb[c] == l && rb[c] == r)
    return make_pair(segmin[c], sminidx[c]);
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r)
    return min(querymin(2 * c, l, k), querymin(2 * c + 1, k + 1, r));
  else if (r <= k)
    return querymin(2 * c, l, r);
  else
    return querymin(2 * c + 1, l, r);
}

pair<int, int> querymax(int c, int l, int r) {
  propmax(c);
  if (lb[c] == l && rb[c] == r)
    return make_pair(segmax[c], smaxidx[c]);
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r)
    return max(querymax(2 * c, l, k), querymax(2 * c + 1, k + 1, r),
               [](pair<int, int> x, pair<int, int> y) {
                 return x.first < y.first   ? true
                        : x.first > y.first ? false
                                            : x.second > y.second;
               });
  else if (r <= k)
    return querymax(2 * c, l, r);
  else
    return querymax(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++) {
    updatemin(1, i, i, r[i]);
    updatemax(1, i, i, r[i]);
  }
  int topptr = 0;
  int botptr = 0;
  for (int it = 0; it < n; it++) {
    int m = querymin(1, 0, n - 1).second;
    bool minfail = false;
    if (m + k < n) {
      auto p = querymin(1, m + k, n - 1);
      if (p.first == 0) {
        m = p.second;
      }
      if (m + k >= n) {
        p = querymin(1, m + k - n, m - 1);
        if (p.first == 0) {
          minfail = true;
        }
      } else {
        minfail = true;
      }
    }
    if (!minfail) {
      // printf("DBG %d\n", m);
      h[m] = n - topptr++;
      if (m >= k - 1) {
        updatemin(1, m - k + 1, m - 1, -1);
      } else {
        if (m != 0) {
          updatemin(1, 0, m - 1, -1);
        }
        updatemin(1, m + n - k + 1, n - 1, -1);
      }
      updatemin(1, m, m, 1e9);
      updatemax(1, m, m, -1e9);
    } else {
      m = querymax(1, 0, n - 1).second;
      if (m + k < n) {
        auto p = querymax(1, m + k, n - 1);
        if (p.first == k - 1) {
          m = p.second;
        }
      }
      h[m] = ++botptr;
      if (m >= k - 1) {
        updatemax(1, m - k + 1, m - 1, 1);
      } else {
        if (m != 0) {
          updatemax(1, 0, m - 1, 1);
        }
        updatemax(1, m + n - k + 1, n - 1, 1);
      }
      updatemin(1, m, m, 1e9);
      updatemax(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