oj.uz

Submission #967892

# Submission time Handle Problem Language Result Execution time Memory
967892 2024-04-23T04:44:11 Z nguyentunglam Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 229964 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[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

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 1 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 38 ms 9220 KB Output is correct
7 Runtime error 747 ms 229964 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 1 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 2 ms 6492 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 107 ms 30148 KB Output is correct
7 Execution timed out 4074 ms 105276 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 107 ms 30148 KB Output is correct
7 Execution timed out 4074 ms 105276 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 Correct 76 ms 48592 KB Output is correct
4 Execution timed out 4098 ms 20888 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 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 10588 KB Output is correct
7 Correct 11 ms 15452 KB Output is correct
8 Correct 14 ms 15600 KB Output is correct
9 Correct 12 ms 13404 KB Output is correct
10 Correct 14 ms 15448 KB Output is correct
11 Correct 11 ms 15448 KB Output is correct
12 Correct 12 ms 15452 KB Output is correct
13 Correct 15 ms 15708 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 32 ms 27736 KB Output is correct
6 Execution timed out 4061 ms 21688 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 1 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 38 ms 9220 KB Output is correct
7 Runtime error 747 ms 229964 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -