oj.uz

Submission #967891

# Submission time Handle Problem Language Result Execution time Memory
967891 2024-04-23T04:43:18 Z nguyentunglam Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 84024 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];

int ans[1010][1010];

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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 40 ms 10408 KB Output is correct
7 Runtime error 601 ms 41008 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 108 ms 14008 KB Output is correct
7 Execution timed out 4080 ms 84024 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 108 ms 14008 KB Output is correct
7 Execution timed out 4080 ms 84024 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6600 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 3 ms 8664 KB Output is correct
7 Correct 11 ms 9560 KB Output is correct
8 Correct 14 ms 9820 KB Output is correct
9 Correct 11 ms 7492 KB Output is correct
10 Correct 13 ms 9820 KB Output is correct
11 Correct 13 ms 9500 KB Output is correct
12 Correct 12 ms 9564 KB Output is correct
13 Correct 14 ms 9820 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 31 ms 11620 KB Output is correct
6 Execution timed out 4054 ms 23620 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 40 ms 10408 KB Output is correct
7 Runtime error 601 ms 41008 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -