oj.uz

Submission #414603

# Submission time Handle Problem Language Result Execution time Memory
414603 2021-05-30T17:55:40 Z abdzag Comparing Plants (IOI20_plants) C++17
11 / 100
 209 ms 12456 KB 
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf = -1e9;

using namespace std;

vector<ll> sorted(3e5);
static const int infint = 1e9;
struct Node {
	Node* l = 0, * r = 0;
	int lo, hi, madd = 0, mset = inf;

	pair<int, int> val = make_pair(-inf, -inf);
	Node(int lo, int hi) :lo(lo), hi(hi) {} // Large interval of -inf
	Node(vector<pair<int, int>>& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo) / 2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = min(l->val, r->val);
		}
		else val = v[lo];
	}
	pair<int, int> query(int L, int R) {
		if (R <= lo || hi <= L) return make_pair(-inf, -inf);
		if (L <= lo && hi <= R) return val;
		push();
		return min(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) mset = val.first = x, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = min(l->val, r->val);
		}
	}
	void add(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			if (mset != inf) mset += x;
			else madd += x;
			val.first += x;
		}
		else {
			push(), l->add(L, R, x), r->add(L, R, x);
			val = min(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo) / 2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset != inf)
			l->set(lo, hi, mset), r->set(lo, hi, mset), mset = inf;
		else if (madd)
			l->add(lo, hi, madd), r->add(lo, hi, madd), madd = 0;
	}
};
ll counter = 0;
vector<bitset<302>> reachable(302);
vector<vector<ll>> g(302);
vector<bool> visited(302);
vector<bool> visited0(302);
void dfs(ll cur) {
	visited[cur] = 1;
	trav(v, g[cur]) {
		if (visited[v] == 0) {
			dfs(v);
		}
		reachable[cur] |= reachable[v];
	}
	return;
}
void extract(Node*& tree, ll cur, ll k, ll n) {
	if (cur - k + 1 < 0) {
		while (!tree->query(0, cur).first) {
			extract(tree, tree->query(0, cur).second, k, n);
		}
		while (!tree->query(n - (k - 1 - cur), n).first) {
			extract(tree, tree->query(n - (k - 1 - cur), n).second, k, n);
		}
		tree->add(0, cur, -1);
		tree->add(n - (k - 1 - cur), n, -1);
		
		rep(j, (n - (k - 1 - cur)), n) {
			if (tree->query(j, j + 1).first < 1e6)g[cur].push_back(j);
		}
		rep(j, 0, cur) {
			if (tree->query(j, j + 1).first < 1e6)g[cur].push_back(j);
		}
	}
	else {
		while (!tree->query(cur - k + 1, cur).first) {
			extract(tree, tree->query(cur - k + 1, cur).second, k, n);
		}
		tree->add(cur - k + 1, cur, -1);
		rep(j, cur - k + 1, cur) {
			if (tree->query(j, j + 1).first < 1e6)g[cur].push_back(j);
		}
	}
	rep(j, cur + 1, cur + k) {
		if (tree->query(j%n, j%n + 1).first < 1e6)g[cur].push_back(j % n);
	}
	tree->set(cur, cur + 1, infint);
	return;
}
void init(int k, std::vector<int> r) {
	ll n = r.size();
	ll indx = 0;
	rep(i, 0, n)reachable[i][i] = 1;
	vector<pair<int, int>> v;
	rep(i, 0, n)v.emplace_back(r[i], i);
	Node* tree = new Node(v, 0, n);
	rep(i, 0, n) {
		pair<int, int> val = tree->query(0, n);
		if (val.first == 0)extract(tree, val.second, k, n);
		else break;
	}
}

int compare_plants(int x, int y) {
	dfs(x);
	dfs(y);
	if (reachable[x][y])return 1;
	else if (reachable[y][x]) return -1;
	return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:119:5: warning: unused variable 'indx' [-Wunused-variable]
  119 |  ll indx = 0;
      |     ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 66 ms 6408 KB Output is correct
7 Runtime error 54 ms 12456 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 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2672 KB Output is correct
6 Runtime error 8 ms 5708 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2672 KB Output is correct
6 Runtime error 8 ms 5708 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2564 KB Output is correct
3 Runtime error 47 ms 12272 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 2764 KB Output is correct
7 Correct 23 ms 3584 KB Output is correct
8 Correct 81 ms 3880 KB Output is correct
9 Correct 23 ms 3584 KB Output is correct
10 Correct 82 ms 3880 KB Output is correct
11 Correct 22 ms 3588 KB Output is correct
12 Correct 29 ms 3640 KB Output is correct
13 Correct 209 ms 4564 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Runtime error 5 ms 5452 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 66 ms 6408 KB Output is correct
7 Runtime error 54 ms 12456 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -