Submission #563027

#	Time	Username	Problem	Language	Result	Execution time	Memory
563027		8e7	Comparing Plants (IOI20_plants)	C++17	100 / 100	1382 ms	76088 KiB

plants

//Challenge: Accepted
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct segtree {
	int seg[4 * maxn], tag[4 * maxn];		
	void push(int cur, int l, int r) {
		if (!tag[cur]) return;
		seg[cur] += tag[cur];
		if (r - l > 1) {
			tag[cur*2] += tag[cur], tag[cur*2+1] += tag[cur];
		}
		tag[cur] = 0;
	}
	void pull(int cur, int l, int r) {
		if (r - l > 1) {
			int m = (l + r) / 2;	
			push(cur*2, l, m), push(cur*2+1, m, r);
		}
		seg[cur] = min(seg[cur*2], seg[cur*2+1]);
	}
	void init(int cur, int l, int r, vector<int> &v) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = v[l];
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, v);
		init(cur*2+1, m, r, v);
		pull(cur, l, r);
	}
	void modify(int cur, int l, int r, int ql, int qr, int v) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += v;	
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, v), modify(cur*2+1, m, r, ql, qr, v);
		pull(cur, l, r);
	}
	void change(int cur, int l, int r, int ind, int v) {
		if (r <= l) return;
		push(cur, l, r);
		if (r - l == 1) {
			seg[cur] = v;
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) change(cur*2, l, m, ind, v);
		else change(cur*2+1, m, r, ind, v);
		pull(cur, l, r);
	}
	int getleft(int cur, int l, int r) {
		if (r <= l) return 0;
		push(cur, l, r);
		if (r - l == 1) return l;
		int m = (l + r) / 2;
		push(cur*2, l, m), push(cur*2+1, m, r);
		if (seg[cur*2] == 0) return getleft(cur*2, l, m);
		else return getleft(cur*2+1, m, r);
	}
	void getzero(int cur, int l, int r, int ql, int qr, vector<int> &v) { // gets all 0's in range [ql, qr)
		if (r <= l || ql >= r || qr <= l) return;	
		push(cur, l, r);
		if (seg[cur] > 0) return;
		if (r - l == 1) {
			v.push_back(l);
			return;
		}
		int m = (l + r) / 2;	
		getzero(cur*2, l, m, ql, qr, v);
		getzero(cur*2+1, m, r, ql, qr, v);
	}
	int query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return inf;
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
	}
	void print(int cur, int l, int r) {
		if (r <= l) return;
		push(cur, l, r);
		if (r - l == 1) {
			debug(seg[cur]);
			return;
		}
		int m = (l + r) / 2;
		print(cur*2, l, m), print(cur*2+1, m, r);
	}
}tr, aux, to;

int n, k;
int lt[18][maxn], rt[18][maxn], cor[maxn], ord[maxn];
int cl[18][maxn], cr[18][maxn];
void init(int K, vector<int> R) {
	n = R.size();
	k = K;
	tr.init(1, 0, n, R);
	aux.init(1, 0, n, R);

	auto add = [&] (int i, int d) {
		aux.modify(1, 0, n, i+1, min(n, i+k), d);	
		if (i + k > n) aux.modify(1, 0, n, 0, i + k - n, d); 	
	};
	for (int i = 0;i < n;i++) {
		to.change(1, 0, n, i, inf); 
		if (R[i] == 0) add(i, 1);
	}

	auto getmi = [&] (int l, int r) { //[l, r]
		int ret = inf;
		if (l < 0) {
			ret = min(to.query(1, 0, n, l+n, n), to.query(1, 0, n, 0, r+1)); 	
		} else if (r >= n) {
			ret = min(to.query(1, 0, n, l, n), to.query(1, 0, n, 0, r - n + 1));
		} else {
			ret = to.query(1, 0, n, l, r+1);
		}
		if (ret > maxn) return -1;
		return cor[ret];
	};
	lt[0][n] = rt[0][n] = n;
	for (int it = n;it > 0;it--) {
		int ind = aux.getleft(1, 0, n);
		add(ind, -1);
		int lef = getmi(ind-k+1, ind-1), rig = getmi(ind+1, ind+k-1);			
		cor[it] = ind, ord[ind] = it;
		to.change(1, 0, n, ind, it);

		if (lef != -1) lt[0][ind] = lef, cl[0][ind] = (lef > ind) ? 1 : 0;
		else lt[0][ind] = n;
		if (rig != -1) rt[0][ind] = rig, cr[0][ind] = (rig < ind) ? 1 : 0;
		else rt[0][ind] = n;

		vector<int> zero;
		tr.change(1, 0, n, ind, inf);
		aux.change(1, 0, n, ind, inf);

		tr.modify(1, 0, n, max(0, ind-k+1), ind, -1);
		aux.modify(1, 0, n, max(0, ind-k+1), ind, -1);
		tr.getzero(1, 0, n, max(0, ind-k+1), ind, zero);
		if (ind - k + 1 < 0) {
			tr.modify(1, 0, n, ind-k+1 + n, n, -1);
			aux.modify(1, 0, n, ind-k+1 + n, n, -1);
			tr.getzero(1, 0, n, ind-k+1 + n, n, zero);
		}
		for (auto i:zero) add(i, 1);	
	}
	pary(ord, ord + n);
	pary(lt[0], lt[0] + n);
	pary(rt[0], rt[0] + n);

	for (int i = 1;i < 18;i++) {
		for (int j = 0;j <= n;j++) {
			lt[i][j] = lt[i-1][lt[i-1][j]];
			cl[i][j] = cl[i-1][j] + cl[i-1][lt[i-1][j]];
			rt[i][j] = rt[i-1][rt[i-1][j]];
			cr[i][j] = cr[i-1][j] + cr[i-1][rt[i-1][j]];
		}
	}
	return;
}

int cdis(int x, int y) {
	if (x > y) swap(x, y);
	return min(abs(x - y), x + n - y);
}
int compare_plants(int x, int y) {
	if (2 * k > n) return (ord[x] < ord[y] ? -1 : 1);
	int tx = x, ty = y;	
	for (int i = 17;i >= 0;i--) {
		if (rt[i][tx] != n && (cr[i][tx] == 0 && rt[i][tx] <= y)) {
			tx = rt[i][tx];
		}
	}
	if (cdis(tx, ty) < k && ord[tx] <= ord[ty]) return -1; 

	tx = x, ty = y;				
	for (int i = 17;i >= 0;i--) {
		if (lt[i][ty] != n && (cl[i][ty] == 0 && lt[i][ty] >= x)) {
			ty = lt[i][ty];
		}
	}
	if (cdis(tx, ty) < k && ord[tx] >= ord[ty]) return 1; 

	tx = x, ty = y;	
	int cnt = 0;
	for (int i = 17;i >= 0;i--) {
		int nxt = lt[i][tx];
		if (nxt != n && ((cl[i][tx] == 1 && !cnt && nxt >= y) || (!cl[i][tx] && (nxt >= y || tx < y)))) {
			cnt += cl[i][tx];
			tx = nxt;
		}
	}
	if (cdis(tx, ty) < k && ord[tx] <= ord[ty]) return -1; 
 
 	tx = x, ty = y, cnt = 0;
	for (int i = 17;i >= 0;i--) {
		int nxt = rt[i][ty];
		if (nxt != n && ((cr[i][ty] == 1 && !cnt && nxt <= x) || (!cr[i][ty] && (nxt <= x || ty > x)))) {
			cnt += cr[i][ty];
			ty = nxt;
		}
	}
	if (cdis(tx, ty) < k && ord[tx] >= ord[ty]) return 1; 
	return 0;
}
/*
4 3 2
0 1 1 2
0 2
1 2

6 2 5
1 0 1 0 0 0
0 1
3 5
0 3
2 4
2 5
*/

Compilation message (stderr)

plants.cpp: In member function 'void segtree::print(int, int, int)':
plants.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
plants.cpp:105:4: note: in expansion of macro 'debug'
  105 |    debug(seg[cur]);
      |    ^~~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
plants.cpp:170:2: note: in expansion of macro 'pary'
  170 |  pary(ord, ord + n);
      |  ^~~~
plants.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
plants.cpp:171:2: note: in expansion of macro 'pary'
  171 |  pary(lt[0], lt[0] + n);
      |  ^~~~
plants.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
plants.cpp:172:2: note: in expansion of macro 'pary'
  172 |  pary(rt[0], rt[0] + n);
      |  ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25