Submission #1147510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147510		abczz	Comparing Plants (IOI20_plants)	C++20	0 / 100	3 ms	4936 KiB

plants

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

ll n, k, nx[200000], A[200000];
vector <ll> adj[200000];
map <ll, ll> mp, mp2, mp3;
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 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 << " " << x << endl;
		adj[it->first].push_back(x);
		mp3.erase(it);
		it = nx;
	}
	it = mp3.begin();
	while (it != mp3.end() && dist(x, it->first)) {
		auto nx = next(it);
    cout << it->first << " " << x << endl;
		adj[it->first].push_back(x);
		mp3.erase(it);
		it = nx;
	}
	it = mp3.lower_bound(x);
  if (it != mp3.begin()) {
    it = prev(it);
  	while (x != it->first) {
  		if (!dist(it->first, x)) break;
  		adj[it->first].push_back(x);
      if (it == mp3.begin()) break;
      auto pv = prev(it);
      mp3.erase(it);
      it = pv;
  	}
  }
	it = mp3.end();
	if (it != mp3.begin()) {
    it = prev(it);
  	while (x != it->first) {
  		if (!dist(it->first, x)) break;
  		adj[it->first].push_back(x);
      if (it == mp3.begin()) break;
      auto pv = prev(it);
      mp3.erase(it);
      it = pv;
  	}
  }
	++mp3[x];
}

void init(int _k, std::vector<int> r) {
  n = r.size(), k = _k;
  mp.clear();
  mp2.clear();
	mp3.clear();
  for (int i=0; i<n; ++i) nx[i] = -1, A[i] = r[i], adj[i].clear();
  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;
		add_edge(u);
    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) {
        nx[U[i]] = U[i+1];
      }
      ++mp[U[0]], ++mp2[U[0]];
      check(U[0]);
    }
    if (nx[u] != -1) {
      ++mp[nx[u]], ++mp2[nx[u]];
      check(nx[u]);
    }
  }
  return;
}

bool visited[200000];
void dfs(ll u) {
  if (visited[u]) return;
  visited[u] = 1;
  for (auto v : adj[u]) {
    if (!visited[v]) dfs(v);
  }
}

bool query(ll x, ll y) {
  for (int i=0; i<n; ++i) visited[i] = 0;
  dfs(x);
  if (visited[y]) return 1;
  else return 0;
}

int compare_plants(int x, int y) {
  if (query(x, y)) return 1;
  else if (query(y, x)) return -1;
  else return 0;
}

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