Submission #968104

#	Time	Username	Problem	Language	Result	Execution time	Memory
968104		nguyentunglam	Comparing Plants (IOI20_plants)	C++17	100 / 100	744 ms	107088 KiB

plants

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

const int N = 2e5 + 10, M = 20;

int p[2 * N], rev_p[N];

int f[M + 1][2 * N], g[M + 1][2 * N];

struct IT1 {
int T[N << 2], lazy[N << 2];;

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);
}
} it1;

struct IT2 {
int T[N << 3];

void up(int s, int l, int r, int pos, int val) {
  if (l == r) {
    T[s] = val;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) up(s << 1, l, mid, pos, val);
  else up(s << 1 | 1, mid + 1, r, pos, val);
  T[s] = max(T[s << 1], T[s << 1 | 1]);
}

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

int n;

int move_right (int i, int val) {
  for(int j = M; j >= 0; j--) {
    if (f[j][i] >= 0 && p[f[j][i]] >= val) i = f[j][i];
  }
  return i;
}

int move_left (int i, int val) {
  for(int j = M; j >= 0; j--) {
    if (g[j][i] >= 0 && p[g[j][i]] >= val) i = g[j][i];
  }
  return i;
}

void init(int k, std::vector<int> r) {
  n = r.size();
  k--;
  for(int i = 0; i < n; i++) it1.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 = it1.get(1, 0, n - 1, max(0, i - k), i - 1);
      if (left >= 0) self(self, left);
      else if (i - k < 0) {
        left = it1.get(1, 0, n - 1, n + i - k, n - 1);
        if (left >= 0) self(self, left);
        else break;
      }
      else break;
    }
    p[i] = val--;
    it1.up(1, 0, n - 1, i, i, 1e9);
    it1.up(1, 0, n - 1, max(0, i - k), i - 1, -1);
    if (i - k < 0) it1.up(1, 0, n - 1, n + i - k, n - 1, -1);
  };

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

  for(int i = 0; i < n; i++) rev_p[p[i]] = i;

  for(int i = 0; i < n; i++) p[i + n] = p[i];

  for(int i = 0; i <= 4 * 2 * n; i++) it2.T[i] = -1;

  for(int val = 0; val < n; val++) {
    int largest;

    int i = rev_p[val];

//    cout << i << endl;
    largest = it2.get(1, 0, 2 * n - 1, i + 1, min(2 * n - 1, i + k));
    f[0][i] = largest >= 0 ? rev_p[largest] : -1;
    largest = it2.get(1, 0, 2 * n - 1, max(0, i - k), i - 1);
    g[0][i] = largest >= 0 ? rev_p[largest] : -1;
    it2.up(1, 0, 2 * n - 1, i, val);
    if (f[0][i] != -1 && f[0][i] < i) f[0][i] += n;
    if (g[0][i] != -1 && g[0][i] + n < i) g[0][i] += n;

    i += n;
    largest = it2.get(1, 0, 2 * n - 1, i + 1, min(2 * n - 1, i + k));
    f[0][i] = largest >= 0 ? rev_p[largest]: -1;
    largest = it2.get(1, 0, 2 * n - 1, max(0, i - k), i - 1);
    g[0][i] = largest >= 0 ? rev_p[largest] : -1;
    it2.up(1, 0, 2 * n - 1, i, val);
    if (f[0][i] != -1 && f[0][i] < i) f[0][i] += n;
    if (g[0][i] != -1 && g[0][i] + n < i) g[0][i] += n;
  }

  for(int j = 1; j <= M; j++) for(int i = 0; i < 2 * n; i++) {
    if (f[j - 1][i] < 0) f[j][i] = -1;
    else f[j][i] = f[j - 1][f[j - 1][i]];

    if (g[j - 1][i] < 0) g[j][i] = -1;
    else g[j][i] = g[j - 1][g[j - 1][i]];
  }
}

int compare_plants(int x, int y) {
  int ret = 1;
  if (p[x] < p[y]) ret = -1, swap(x, y);
  if (x < y) x += n;
  if (move_left(x, p[y]) <= y) return ret;
  if (move_right(x, p[y]) >= y + n) return ret;
  return 0;
}

#ifdef ngu
int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
  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;
	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 member function 'void IT1::up(int, int, int, int, int, int)':
plants.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid = l + r >> 1;
      |             ~~^~~
plants.cpp: In member function 'int IT1::get(int, int, int, int, int)':
plants.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid = l + r >> 1;
      |             ~~^~~
plants.cpp: In member function 'void IT2::up(int, int, int, int, int)':
plants.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   int mid = l + r >> 1;
      |             ~~^~~
plants.cpp: In member function 'int IT2::get(int, int, int, int, int)':
plants.cpp:67:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int mid = l + r >> 1;
      |             ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:95:8: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
   95 |   auto calc = [&] () {
      |        ^~~~

• 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