Submission #1147613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147613		abczz	Comparing Plants (IOI20_plants)	C++20	100 / 100	594 ms	159728 KiB

plants

#include "plants.h"
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;

ll n, k, t, nx[200000], A[200000], L[200000], R[200000], T[200000], bl[2][200000][18], ps[2][200000][18];
map <ll, ll> mp, mp2, mp3, mp4;
vector <ll> V, U;
struct SegTree{
  ll st[800000], lazy[800000];
  void build(ll id, ll l, ll r) {
    lazy[id] = 0;
    if (l == r) {
      st[id] = A[l];
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = min(st[id*2], st[id*2+1]);
  }
  void push_down(ll id) {
    st[id*2] -= lazy[id];
    st[id*2+1] -= lazy[id];
    lazy[id*2] += lazy[id];
    lazy[id*2+1] += lazy[id];
    lazy[id] = 0;
  }
  void update(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      ++lazy[id];
      --st[id];
      query(id, l, r);
      return;
    }
    push_down(id);
    ll mid = (l+r)/2;
    update(id*2, l, mid, ql, qr);
    update(id*2+1, mid+1, r, ql, qr);
    st[id] = min(st[id*2], st[id*2+1]);
  }
  void query(ll id, ll l, ll r) {
    if (st[id] > 0) return;
    if (l == r) {
      st[id] = 1e18;
      U.push_back(l);
      return;
    }
    push_down(id);
    ll mid = (l+r)/2;
    query(id*2, l, mid);
    query(id*2+1, mid+1, r);
    st[id] = min(st[id*2], st[id*2+1]);
  }
}ST;

bool dist(ll a, ll b) {
  if (a <= b) return (b-a < k ? 1 : 0);
  else return (b-a+n < k ? 1 : 0);
}

void fix(ll x) {
  auto it = mp.lower_bound(x);
  if (it != mp.end() && dist(x, it->first)) {
    nx[x] = it->first;
    mp.erase(it);
    return;
  }
  it = mp.begin();
  if (it != mp.end() && dist(x, it->first)) {
    nx[x] = it->first;
    mp.erase(it);
    return;
  }
}

void check(ll x) {
  auto it = mp2.lower_bound(x);
  if (it != mp2.begin()) {
    it = prev(it);
    if (dist(it->first, x)) {
      mp.erase(x);
      nx[it->first] = x;
      return;
    }
  }
  else if (mp2.size() != 1) {
    it = prev(mp2.end());
    if (dist(it->first, x)) {
      mp.erase(x);
      nx[it->first] = x;
      return;
    }
  }
}

void add_edge(ll x) {
	auto it = mp3.lower_bound(x);
	while (it != mp3.end() && dist(x, it->first)) {
		auto nx = next(it);
    //cout << it->first << "L" << x << endl;
		L[it->first] = x;
		mp3.erase(it);
		it = nx;
	}
	it = mp3.begin();
	while (it != mp3.end() && dist(x, it->first)) {
		auto nx = next(it);
    //cout << it->first << "L" << x << endl;
		L[it->first] = x;
		mp3.erase(it);
		it = nx;
	}
	it = mp4.lower_bound(x);
  if (it != mp4.begin()) {
    it = prev(it);
  	while (x != it->first) {
  		if (!dist(it->first, x)) break;
      //cout << it->first << "R" << x << endl;
  		R[it->first] = x;
      if (it == mp4.begin()) {
        mp4.erase(it);
        break;
      }
      auto pv = prev(it);
      mp4.erase(it);
      it = pv;
  	}
  }
	it = mp4.end();
	if (it != mp4.begin()) {
    it = prev(it);
  	while (x != it->first) {
  		if (!dist(it->first, x)) break;
  		R[it->first] = x;
      //cout << it->first << "R" << x << endl;
      if (it == mp4.begin()) {
        mp4.erase(it);
        break;
      }
      auto pv = prev(it);
      mp4.erase(it);
      it = pv;
  	}
  }
	++mp3[x], ++mp4[x];
}

void init(int _k, std::vector<int> r) {
  n = r.size(), k = _k, t = 0;
  mp.clear();
  mp2.clear();
	mp3.clear();
  mp4.clear();
  for (int i=0; i<n; ++i) nx[i] = -1, A[i] = r[i], L[i] = R[i] = i;
  for (int i=0; i<n; ++i) {
    if (A[i] == 0) V.push_back(i), ++mp[i], ++mp2[i], A[i] = 1e18;
  }
  ST.build(1, 0, n-1);
  for (int i=0; i+1<V.size(); ++i) {
    if (dist(V[i], V[i+1])) {
      mp.erase(V[i+1]);
      nx[V[i]] = V[i+1];
    }
  }
  if (V.size() != 1 && dist(V.back(), V[0])) {
    mp.erase(V[0]);
    nx[V.back()] = V[0];
  }
  while (!mp.empty()) {
    auto it = mp.begin();
    ll u = it->first;
    T[u] = t++;
		add_edge(u);
    //cout << u << endl;
    mp.erase(it);
    mp2.erase(u);
    ll l = (u-k+1+n)%n, r = (u-1+n)%n;
    U.clear();
    if (l <= r) ST.update(1, 0, n-1, l, r);
    else {
      ST.update(1, 0, n-1, l, n-1);
      ST.update(1, 0, n-1, 0, r);
    }
    if (!U.empty()) {
      for (int i=0; i+1<U.size(); ++i) {
        ++mp2[U[i]];
        nx[U[i]] = U[i+1];
      }
      ++mp2[U.back()];
      fix(U[0]);
      ++mp[U[0]];
      check(U[0]);
    }
    if (nx[u] != -1) {
      fix(nx[u]);
      ++mp[nx[u]], ++mp2[nx[u]];
      check(nx[u]);
    }
  }
  for (int i=0; i<n; ++i) {
    ps[0][i][0] = (i-L[i]+n) % n;
    bl[0][i][0] = L[i];
    ps[1][i][0] = (R[i]-i+n) % n;
    bl[1][i][0] = R[i];
  }
  for (int j=1; j<18; ++j) {
    for (int i=0; i<n; ++i) {
      for (int x=0; x<2; ++x) {
        bl[x][i][j] = bl[x][bl[x][i][j-1]][j-1];
        ps[x][i][j] = ps[x][i][j-1] + (bl[x][i][j-1] != i ? ps[x][bl[x][i][j-1]][j-1] : 0);
      }
    }
  }
  return;
}

ll query(ll x, ll y) {
  //cout << x << "*" << y << endl;
  ll u = x, d = (x-y+n) % n;
  for (int j=17; j>=0; --j) {
    if (ps[0][u][j] <= d) {
      d -= ps[0][u][j];
      u = bl[0][u][j];
    }
  }
  if (T[u] <= T[y] && dist(y, u)) return 1;
  //cout << u << " " << y << endl;
  u = x, d = (y-x+n) % n;
  for (int j=17; j>=0; --j) {
    if (ps[1][u][j] <= d) {
      d -= ps[1][u][j];
      u = bl[1][u][j];
    }
  }
  if (T[u] <= T[y] && dist(u, y)) return 1;
  //cout << u << " " << y << endl;
  return 0;
}
int compare_plants(int x, int y) {
  if (T[x] < T[y]) return query(x, y);
  else return -query(y, x);
}

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