oj.uz

Submission #823511

# Submission time Handle Problem Language Result Execution time Memory
823511 2023-08-12T16:01:35 Z NothingXD Comparing Plants (IOI20_plants) C++17
0 / 100
 7 ms 9684 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const int inf = 1e6;

int n, k, a[maxn], ver[maxn], seg[maxn << 2][3], lazy[maxn << 2][3];
vector<int> g[maxn][2];
bool vis[maxn][2];

void shift(int v, int x, int l, int r);

void add(int v, int x, int l, int r, int ql, int qr, int val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v][x] += val;
		lazy[v][x] += val;
		return;
	}
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, ql, qr, val);
	add(v << 1 | 1, x, mid, r, ql, qr, val);
	seg[v][x] = min(seg[v<<1][x], seg[v<<1|1][x]);
}

int find0(int v, int x, int l, int r){
	if (seg[v][x] != 0) return -1;
	if (l + 1 == r) return l;
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	int res = find0(v << 1, x, l, mid);
	if (res == -1) return find0(v << 1 | 1, x, mid, r);
	return res;
}

void shift(int v, int x, int l, int r){
	if (lazy[v][x] == 0) return;
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, l, mid, lazy[v][x]);
	add(v << 1 | 1, x, mid, r, mid, r, lazy[v][x]);
	lazy[v][x] = 0;
}

int get(int v, int x, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return inf;
	if (ql <= l && r <= qr) return seg[v][x];
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	return min(get(v << 1, x, l, mid, ql, qr)
			, get(v << 1 | 1, x, mid, r, ql, qr));
}

void dfs(int v, int x){
	vis[v][x] = true;
	for (auto u: g[v][x]){
		if (!vis[u][x]) dfs(u, x);
	}
}

void init(int _k, std::vector<int> r) {
	n = r.size();
	k = _k;
	for (int i = 0; i < n; i++){
		a[i] = r[i];
		add(1, 0, 0, n, i, i+1, a[i]);
		add(1, 1, 0, n, i, i+1, a[i]);
		add(1, 2, 0, n, i, i+1, inf);
	}
	vector<int> topol;
	for (int i = 0; i < n; i++){
		int tmp;
		while((tmp = find0(1, 1, 0, n)) != -1){
			add(1, 0, 0, n, tmp+1, tmp+k, 1);
			if (tmp+k > n){
				add(1, 0, 0, n, 0, tmp+k-n, 1);
			}
			add(1, 1, 0, n, tmp, tmp+1, inf);
		}
		tmp = find0(1, 0, 0, n);
		add(1, 0, 0, n, tmp+1, tmp+k, -1);
		if (tmp+k > n){
			add(1, 0, 0, n, 0, tmp+k-n, -1);
		}
		add(1, 0, 0, n, tmp-k+1, tmp, -1);
		add(1, 1, 0, n, tmp-k+1, tmp, -1);
		if (tmp-k+1 < 0){
			add(1, 0, 0, n, tmp-k+1+n, n, -1);
			add(1, 1, 0, n, tmp-k+1+n, n, -1);
		}
		int mn1 = get(1, 2, 0, n, tmp+1, tmp+k);
		int mn2 = get(1, 2, 0, n, tmp-k+1, tmp);
		if (tmp+k > n){
			mn1 = min(mn1, get(1, 2, 0, n, 0, tmp+k-n));
		}
		if (tmp-k+1 < 0){
			mn2 = min(mn2, get(1, 2, 0, n, tmp-k+1+n, n));
		}
	//	debug(tmp);
		if (mn1 != inf){
			g[ver[mn1]][0].push_back(tmp);
			g[tmp][0].push_back(ver[mn1]);
	//		debug(ver[mn1], tmp);
		}
		if (mn2 != inf){
			g[ver[mn2]][0].push_back(tmp);
			g[tmp][0].push_back(ver[mn2]);
	//		debug(ver[mn2], tmp);
		}
		ver[n-i] = tmp;
		assert(tmp != -1);
		add(1, 0, 0, n, tmp, tmp+1, inf);
		add(1, 2, 0, n, tmp, tmp+1, (n-i)-inf);
	}
//	debug(1);
	dfs(0, 0);
	dfs(0, 1);
}

int compare_plants(int x, int y) {
	return (vis[y][0]? 1: (vis[y][1]? -1: 0));
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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