oj.uz

답안 #826316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826316 2023-08-15T12:49:01 Z NothingXD 식물 비교 (IOI20_plants) C++17
0 / 100
 120 ms 3812 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 lg = 20;
const int inf = 1e6;

int n, k, a[maxn], idx[maxn], ver[maxn], seg[maxn << 2][3], lazy[maxn << 2][3];
ll par[2][maxn][lg];

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 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 rng = 0; rng < n; rng++){
		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));
		}
		if (mn1 != inf){
//			debug(tmp, ver[mn1]);
			par[0][tmp][0] = (ver[mn1]-tmp+n) % n;
			for (int i = 1; i < lg; i++){
				par[0][tmp][i] = par[0][tmp][i-1] + par[0][(tmp+par[0][tmp][i-1])%n][i-1];
//				debug(i, par[0][tmp][i]);
			}
		}
		if (mn2 != inf){
//			debug(tmp, ver[mn2]);
			par[1][tmp][0] = (tmp-ver[mn2]+n) % n;
			for (int i = 1; i < lg; i++){
				par[1][tmp][i] = par[0][tmp][i-1] + par[1][(tmp-par[1][tmp][i-1]+n)%n][i-1];
//				debug(i, par[1][tmp][i]);
			}
		}
		ver[n-rng] = tmp;
		idx[tmp] = n-rng;
		assert(tmp != -1);
		add(1, 0, 0, n, tmp, tmp+1, inf);
		add(1, 2, 0, n, tmp, tmp+1, (n-rng)-inf);
	}
}

bool ok(int x, int y){
//	debug(x, y);
	int v = x;
	int dis = (y - x + n) % n;
//	debug(v, dis);
	for (int i = lg-1; ~i; i--){
		if (par[0][v][i] <= dis){
			dis -= par[0][v][i];
			v = (v+par[0][v][i]) % n;
		}
	}
//	debug(v);
	if (v == y || (idx[y] > idx[v] && dis < k)) return true;
	v = x;
	dis = (x - y + n) % n;
//	debug(v, dis);
	for (int i = lg-1; ~i; i--){
		if (par[1][v][i] <= dis){
			dis -= par[1][v][i];
			v = (v-par[1][v][i]+n) % n;
		}
	}
	//debug(v);
	if (v == y || (idx[y] > idx[v] && dis < k)) return true;
	return false;
}

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 120 ms 3812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 4 ms 724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -