oj.uz

Submission #968101

# Submission time Handle Problem Language Result Execution time Memory
968101 2024-04-23T07:41:31 Z nguyentunglam Comparing Plants (IOI20_plants) C++17
25 / 100
 346 ms 77960 KB 
#include<bits/stdc++.h>
using namespace std;
#include "plants.h"

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

int p[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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65876 KB Output is correct
2 Correct 7 ms 65884 KB Output is correct
3 Correct 8 ms 68148 KB Output is correct
4 Correct 9 ms 67928 KB Output is correct
5 Correct 8 ms 65880 KB Output is correct
6 Correct 59 ms 69804 KB Output is correct
7 Correct 107 ms 76196 KB Output is correct
8 Runtime error 196 ms 25844 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66080 KB Output is correct
2 Correct 9 ms 65884 KB Output is correct
3 Correct 9 ms 66108 KB Output is correct
4 Correct 8 ms 65884 KB Output is correct
5 Correct 8 ms 68188 KB Output is correct
6 Correct 11 ms 68284 KB Output is correct
7 Correct 74 ms 75092 KB Output is correct
8 Correct 9 ms 68120 KB Output is correct
9 Correct 10 ms 68260 KB Output is correct
10 Correct 68 ms 75140 KB Output is correct
11 Correct 90 ms 73332 KB Output is correct
12 Correct 75 ms 75288 KB Output is correct
13 Correct 68 ms 75088 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 66080 KB Output is correct
2 Correct 9 ms 65884 KB Output is correct
3 Correct 9 ms 66108 KB Output is correct
4 Correct 8 ms 65884 KB Output is correct
5 Correct 8 ms 68188 KB Output is correct
6 Correct 11 ms 68284 KB Output is correct
7 Correct 74 ms 75092 KB Output is correct
8 Correct 9 ms 68120 KB Output is correct
9 Correct 10 ms 68260 KB Output is correct
10 Correct 68 ms 75140 KB Output is correct
11 Correct 90 ms 73332 KB Output is correct
12 Correct 75 ms 75288 KB Output is correct
13 Correct 68 ms 75088 KB Output is correct
14 Correct 108 ms 77960 KB Output is correct
15 Runtime error 346 ms 27816 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 63836 KB Output is correct
2 Correct 11 ms 67932 KB Output is correct
3 Correct 77 ms 64580 KB Output is correct
4 Runtime error 226 ms 37220 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 62044 KB Output is correct
2 Correct 9 ms 66000 KB Output is correct
3 Correct 7 ms 65884 KB Output is correct
4 Correct 8 ms 68040 KB Output is correct
5 Correct 9 ms 68188 KB Output is correct
6 Correct 10 ms 68188 KB Output is correct
7 Correct 22 ms 69028 KB Output is correct
8 Correct 19 ms 69068 KB Output is correct
9 Correct 20 ms 66908 KB Output is correct
10 Correct 19 ms 68956 KB Output is correct
11 Correct 20 ms 68956 KB Output is correct
12 Correct 23 ms 68956 KB Output is correct
13 Correct 18 ms 69108 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 65880 KB Output is correct
2 Correct 8 ms 66068 KB Output is correct
3 Correct 9 ms 67932 KB Output is correct
4 Correct 7 ms 66064 KB Output is correct
5 Correct 11 ms 68144 KB Output is correct
6 Runtime error 248 ms 26320 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65876 KB Output is correct
2 Correct 7 ms 65884 KB Output is correct
3 Correct 8 ms 68148 KB Output is correct
4 Correct 9 ms 67928 KB Output is correct
5 Correct 8 ms 65880 KB Output is correct
6 Correct 59 ms 69804 KB Output is correct
7 Correct 107 ms 76196 KB Output is correct
8 Runtime error 196 ms 25844 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -