oj.uz

Submission #967890

# Submission time Handle Problem Language Result Execution time Memory
967890 2024-04-23T04:30:51 Z nguyentunglam Comparing Plants (IOI20_plants) C++17
44 / 100
 362 ms 27220 KB 
#include<bits/stdc++.h>
using namespace std;
#include "plants.h"

const int N = 2e5 + 10;

int p[N], 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);
}

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

//  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 (p[x] < p[y]) return -1;
	return 1;
}

#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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 43 ms 7252 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 43 ms 7432 KB Output is correct
11 Correct 41 ms 5464 KB Output is correct
12 Correct 41 ms 7436 KB Output is correct
13 Correct 44 ms 7260 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 43 ms 7252 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 43 ms 7432 KB Output is correct
11 Correct 41 ms 5464 KB Output is correct
12 Correct 41 ms 7436 KB Output is correct
13 Correct 44 ms 7260 KB Output is correct
14 Correct 66 ms 7764 KB Output is correct
15 Correct 353 ms 11468 KB Output is correct
16 Correct 65 ms 9812 KB Output is correct
17 Correct 361 ms 14936 KB Output is correct
18 Correct 287 ms 20256 KB Output is correct
19 Correct 275 ms 15116 KB Output is correct
20 Correct 362 ms 14928 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 40 ms 5224 KB Output is correct
4 Correct 249 ms 12828 KB Output is correct
5 Correct 311 ms 11092 KB Output is correct
6 Correct 314 ms 11088 KB Output is correct
7 Correct 348 ms 11016 KB Output is correct
8 Correct 353 ms 14672 KB Output is correct
9 Correct 267 ms 16492 KB Output is correct
10 Correct 259 ms 15732 KB Output is correct
11 Correct 232 ms 27220 KB Output is correct
12 Correct 271 ms 14264 KB Output is correct
13 Correct 282 ms 23312 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -