oj.uz

Submission #823512

# Submission time Handle Problem Language Result Execution time Memory
823512 2023-08-12T16:02:37 Z NothingXD Comparing Plants (IOI20_plants) C++17
15 / 100
 1276 ms 44256 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][1].push_back(ver[mn1]);
	//		debug(ver[mn1], tmp);
		}
		if (mn2 != inf){
			g[ver[mn2]][0].push_back(tmp);
			g[tmp][1].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 5 ms 9684 KB Output is correct
2 Correct 4 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 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Incorrect 4 ms 9724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Incorrect 4 ms 9724 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 9660 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 9684 KB Output is correct
3 Incorrect 4 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9696 KB Output is correct
3 Correct 5 ms 9648 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 8 ms 9780 KB Output is correct
6 Correct 833 ms 40756 KB Output is correct
7 Correct 1026 ms 41108 KB Output is correct
8 Correct 1165 ms 42824 KB Output is correct
9 Correct 1276 ms 44256 KB Output is correct
10 Correct 729 ms 42024 KB Output is correct
11 Correct 999 ms 43636 KB Output is correct
12 Correct 697 ms 43372 KB Output is correct
13 Correct 840 ms 42652 KB Output is correct
14 Correct 1104 ms 42736 KB Output is correct
15 Correct 1241 ms 43092 KB Output is correct
16 Correct 719 ms 43192 KB Output is correct
17 Correct 819 ms 42396 KB Output is correct

Subtask #7
0 / 25.0

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