제출 #1306401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306401		Jasonwei	장애물 (IOI25_obstacles)	C++20	100 / 100	308 ms	107980 KiB

obstacles

/*
-A2 --indent=tab=4 --indent-classes --indent-switches --indent-namespaces --indent-preprocessor -xg -p -xd -H -xj -xe

read all problems
do first-eye problems
read rev order

uhhh dont fail impl
*/
#include <bits/stdc++.h>
#include "obstacles.h"
#define ll long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms(a, b) memset(a, b, sizeof (a))
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
template <typename T> bool chkmin (T &a, T b) {
	return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T &a, T b) {
	return (b > a) ? a = b, 1 : 0;
}
using namespace std;
const int N = 2e5 + 5;
int T, n, m, a[N], b[N], w[N], h[N], z[N][20], st[N], lf[N], rf[N], f[N][20], vl[N][20], vr[N][20], L[N][20], R[N][20];
bool lc[N], rc[N];
int qry (int l, int r) {
	int k = __lg (r - l + 1);
	return max (z[l][k], z[r - (1 << k) + 1][k]);
}
bool chk (int x, int y) {
	return w[min (a[x], a[y])] > qry (x, y);
}
void initialize (vector <int> T, vector <int> H) {
	n = T.size (), m = H.size ();
	re (i, 1, n, 1) w[i] = max (w[i - 1], T[i - 1]);
	re (i, 1, n - 1, 1) chkmin (T[i], T[i - 1]);
	re (i, 1, m, 1)	z[i][0] = h[i] = H[i - 1], a[i] = lower_bound (T.begin (), T.end (), h[i], greater<>()) - T.begin();
	re (k, 1, 19, 1) re (i, 1, m + 1 - (1 << k), 1) z[i][k] = max (z[i][k - 1], z[i + (1 << (k - 1))][k - 1]);
	re (i, 0, m + 1, 1) R[i][0] = rf[i] = m + 1;
	vector <PII> vo;
	re (i, 1, m, 1) if (a[i]) vo.eb (h[i], i);
	sort (vo.begin (), vo.end ());
	re (i, 0, vo.size () - 1, 1) b[vo[i].S] = i + 1;
	int tp = 0;
	re (i, 1, m, 1) if (a[i]) {
		for (; tp && b[st[tp]] > b[i]; tp --) rf[st[tp]] = i;	
		lf[i] = st[tp], st[++ tp] = i;
	}
	re (i, 1, m, 1) if (a[i]) {
		if (lf[i] >= 1 && (lc[i] = chk (lf[i], i))) L[i][0] = lf[i];
		if (rf[i] <= m && (rc[i] = chk (i, rf[i]))) R[i][0] = rf[i];
	}
	de (i, (int)vo.size () - 1, 0, 1) {
		int x = vo[i].S, d = b[lf[x]] < b[rf[x]];
		if (! lc[x] && ! rc[x]) f[x][0] = 0;
		else if (! rc[x]) f[x][0] = lf[x];
		else if (! lc[x]) f[x][0] = rf[x];
		else f[x][0] = (d ? lf[x] : rf[x]);
		vl[x][0] = vr[x][0] = f[x][0];
	}
	int p = 0;
	re (k, 1, 19, 1) re (i, 0, m + 1, 1) {
		L[i][k] = L[L[i][k - 1]][k - 1], R[i][k] = R[R[i][k - 1]][k - 1], p = f[i][k - 1], f[i][k] = f[p][k - 1];
		vl[i][k] = min (vl[i][k - 1], vl[p][k - 1]), vr[i][k] = max (vr[i][k - 1], vr[p][k - 1]);
	}
}
int qry (int l, int r, int x) {
	de (k, 19, 0, 1) if (l <= vl[x][k] && vr[x][k] <= r) x = f[x][k];
	while (l <= L[x][0] || R[x][0] <= r) {
		de (k, 19, 0, 1) if (L[x][k] >= l) x = L[x][k];
		de (k, 19, 0, 1) if (R[x][k] <= r) x = R[x][k];
	}
	return x;
}
bool can_reach (int l, int r, int u, int v) {
	l ++, r ++, u ++, v ++;
	return qry (l, r, u) == qry (l, r, v);
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 21 / 21
• Subtask 5: 25 / 25
• Subtask 6: 17 / 17