Submission #967892

#	Time	Username	Problem	Language	Result	Execution time	Memory
967892		nguyentunglam	Comparing Plants (IOI20_plants)	C++17	11 / 100	4098 ms	229964 KiB

plants

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

const int N = 2e5 + 10;

int p[N], T[N << 2], lazy[N << 2];

int ans[5010][5010];

vector<int> adj[N];

bool vis[N];

void expand (int u) {
  vis[u] = 1;
  for(int &v : adj[u]) if (!vis[v]) expand(v);
}

void push(int s, int l, int r) {
  if (!lazy[s]) return;
  T[s] += lazy[s];
  if (l != r) {
    lazy[s << 1] += lazy[s];
    lazy[s << 1 | 1] += lazy[s];
  }
  lazy[s] = 0;
}

void up(int s, int l, int r, int from, int to, int val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    lazy[s] = val;
    push(s, l, r);
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
  T[s] = min(T[s << 1], T[s << 1 | 1]);
}

int get(int s, int l, int r, int from, int to) {
  push(s, l, r);
  if (l > to || r < from || T[s]) return -1;
  if (l == r) return l;
  int mid = l + r >> 1;

  int ret = get(s << 1 | 1, mid + 1, r, from, to);
  if (ret >= 0) return ret;
  return get(s << 1, l, mid, from, to);
}

void init(int k, std::vector<int> r) {
  int n = r.size();
  k--;
  for(int i = 0; i < n; i++) up(1, 0, n - 1, i, i, r[i]);

  int val = n - 1;

  auto calc = [&] () {
    int m = n;
    vector<int> ret(m);
    for(int i = 0; i < m; i++) {
      for(int j = i; j <= i + k; j++) ret[i] += p[i] < p[j % m];
    }
    return ret;
  };

  auto dfs = [&] (auto self, int i) -> void {
    while (1) {
      int left = get(1, 0, n - 1, max(0, i - k), i - 1);
      if (left >= 0) self(self, left);
      else if (i - k < 0) {
        left = get(1, 0, n - 1, n + i - k, n - 1);
        if (left >= 0) self(self, left);
        else break;
      }
      else break;
    }
    p[i] = val--;
    up(1, 0, n - 1, i, i, 1e9);
    up(1, 0, n - 1, max(0, i - k), i - 1, -1);
    if (i - k < 0) up(1, 0, n - 1, n + i - k, n - 1, -1);
//    cout << get(1, 0, n - 1, 2, 2) << endl;
  };

  while (1) {
    int pos = get(1, 0, n - 1, 0, n - 1);
    if (pos < 0) break;
    dfs(dfs, pos);
  }

  for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) {
    int dist = min(abs(j - i), n - abs(j - i));
    if (dist <= k) {
      if (p[i] > p[j]) adj[i].push_back(j);
      else adj[j].push_back(i);
    }
  }

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) vis[j] = 0;
    expand(i);
    for(int j = 0; j < n; j++) ans[i][j] = vis[j];
  }

//  vector<int> tmp = calc();
//  assert(tmp == r);
//  for(int &j : tmp) cout << j << " "; cout << endl;

//  for(int i = 0; i < n; i++) cout << p[i] << " "; cout << endl;
}

int compare_plants(int x, int y) {
	if (ans[x][y]) return 1;
  if (ans[y][x]) return -1;
  return 0;
}

#ifdef ngu
static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}
#endif // ngu

Compilation message (stderr)

plants.cpp: In function 'void up(int, int, int, int, int, int)':
plants.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
plants.cpp: In function 'int get(int, int, int, int, int)':
plants.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = l + r >> 1;
      |             ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:62:8: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
   62 |   auto calc = [&] () {
      |        ^~~~

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