Submission #601896

#	Time	Username	Problem	Language	Result	Execution time	Memory
601896		model_code	Giraffes (JOI22_giraffes)	C++17	100 / 100	2868 ms	2052 KiB

giraffes

/*
	100-POINT SOLUTION FOR "GIRAFFES" (JOI 2022 OPEN CONTEST)
	- Solution: Speeding up dynamic programming with sweepline algorithm using segment tree
	- Time Complexty: O(N log N * (N - answer)) (= O(N^1.5 log N) for average case)
*/

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class segtree {
private:
	int sz;
	std::vector<int> val;
public:
	static const int INF = 2012345678;
	segtree() : sz(0), val(std::vector<int>()) {};
	segtree(int n) {
		sz = 1;
		while (sz < n) {
			sz *= 2;
		}
		val = std::vector<int>(sz * 2, INF);
	}
	void reset() {
		for (int i = 0; i < sz * 2; i++) {
			val[i] = INF;
		}
	}
	void upgrade(int pos, int x) {
		pos += sz;
		val[pos] = std::min(val[pos], x);
		while (pos > 1) {
			pos >>= 1;
			val[pos] = std::min(val[pos * 2], val[pos * 2 + 1]);
		}
	}
	int rangemin(int l, int r) {
		l += sz;
		r += sz;
		int answer = INF;
		while (l != r) {
			if ((l & 1) == 1) answer = std::min(answer, val[l++]);
			if ((r & 1) == 1) answer = std::min(answer, val[--r]);
			l >>= 1;
			r >>= 1;
		}
		return answer;
	}
};

class square {
public:
	int x, y, l;
	square() : x(0), y(0), l(0) {};
	square(int x_, int y_, int l_) : x(x_), y(y_), l(l_) {};
};

int solve(int N, const vector<int>& P) {
	// dp[i][j]: smallest size of square of "answer = t" with point (j, P[j]) at direction i
	const int INF = 1012345678;
	vector<vector<int> > dp(4, vector<int>(N, 0));
	int t = 1;
	
	// step #0. preparation
	vector<int> pa(N), pb(N);
	for (int i = 0; i < N; i++) {
		pa[i] = i;
		pb[i] = i;
	}
	sort(pa.begin(), pa.end(), [&](int i, int j) { return i - P[i] < j - P[j]; });
	sort(pb.begin(), pb.end(), [&](int i, int j) { return i + P[i] < j + P[j]; });
	
	while (true) {
		// step #1. enumerate all squares
		vector<square> sq;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < N; j++) {
				if (dp[i][j] != INF) {
					int x = j - (i & 2 ? dp[i][j] : 0);
					int y = P[j] - (i & 1 ? dp[i][j] : 0);
					sq.push_back(square(x, y, dp[i][j]));
				}
			}
		}
		int S = sq.size();
		
		// step #2. preparation
		dp = vector<vector<int> >(4, vector<int>(N, INF));
		vector<square> sqa = sq;
		sort(sqa.begin(), sqa.end(), [](const square& s1, const square& s2) { return s1.x - s1.y < s2.x - s2.y; });
		vector<square> sqb = sq;
		sort(sqb.begin(), sqb.end(), [](const square& s1, const square& s2) { return s1.x + s1.y + s1.l < s2.x + s2.y + s2.l; });
		segtree seg1(N);
		segtree seg2(N);
		int posp, possq;
		
		// step #3. sweepline by increasing x-y
		seg1.reset();
		seg2.reset();
		posp = 0;
		possq = 0;
		while (posp != N || possq != S) {
			int px = pa[posp];
			int py = P[pa[posp]];
			int v1 = (posp != N ? px - py : INF);
			int v2 = (possq != S ? sqa[possq].x - sqa[possq].y : INF);
			if (v1 >= v2) {
				seg1.upgrade(sqa[possq].x, sqa[possq].y + sqa[possq].l);
				seg2.upgrade(sqa[possq].y + sqa[possq].l, -sqa[possq].x);
				possq += 1;
			}
			else {
				dp[0][px] = min(dp[0][px], seg1.rangemin(px + 1, N) - py);
				dp[3][px] = min(dp[3][px], px - (-seg2.rangemin(0, py)));
				posp += 1;
			}
		}
		
		// step #4. sweepline by decreasing x-y
		seg1.reset();
		seg2.reset();
		posp = N - 1;
		possq = S - 1;
		while (posp != -1 || possq != -1) {
			int px = pa[posp];
			int py = P[pa[posp]];
			int v1 = (posp != -1 ? px - py : -INF);
			int v2 = (possq != -1 ? sqa[possq].x - sqa[possq].y : -INF);
			if (v1 <= v2) {
				seg1.upgrade(sqa[possq].y, sqa[possq].x + sqa[possq].l);
				seg2.upgrade(sqa[possq].x + sqa[possq].l, -sqa[possq].y);
				possq -= 1;
			}
			else {
				dp[0][px] = min(dp[0][px], seg1.rangemin(py + 1, N) - px);
				dp[3][px] = min(dp[3][px], py - (-seg2.rangemin(0, px)));
				posp -= 1;
			}
		}
		
		// step #5. sweepline by increasing x+y
		seg1.reset();
		seg2.reset();
		posp = 0;
		possq = 0;
		while (posp != N || possq != S) {
			int px = pb[posp];
			int py = P[pb[posp]];
			int v1 = (posp != N ? px + py : INF);
			int v2 = (possq != S ? sqb[possq].x + sqb[possq].y + sqb[possq].l : INF);
			if (v1 >= v2) {
				seg1.upgrade(sqb[possq].x, -sqb[possq].y);
				seg2.upgrade(sqb[possq].y, -sqb[possq].x);
				possq += 1;
			}
			else {
				dp[1][px] = min(dp[1][px], py - (-seg1.rangemin(px + 1, N)));
				dp[2][px] = min(dp[2][px], px - (-seg2.rangemin(py + 1, N)));
				posp += 1;
			}
		}
		
		// step #6. sweepline by decreasing x+y
		seg1.reset();
		seg2.reset();
		posp = N - 1;
		possq = S - 1;
		while (posp != -1 || possq != -1) {
			int px = pb[posp];
			int py = P[pb[posp]];
			int v1 = (posp != -1 ? px + py : -INF);
			int v2 = (possq != -1 ? sqb[possq].x + sqb[possq].y + sqb[possq].l : -INF);
			if (v1 <= v2) {
				seg1.upgrade(sqb[possq].y + sqb[possq].l, sqb[possq].x + sqb[possq].l);
				seg2.upgrade(sqb[possq].x + sqb[possq].l, sqb[possq].y + sqb[possq].l);
				possq -= 1;
			}
			else {
				dp[1][px] = min(dp[1][px], seg1.rangemin(0, py) - px);
				dp[2][px] = min(dp[2][px], seg2.rangemin(0, px) - py);
				posp -= 1;
			}
		}
		
		// step #7. final cleanup
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < N; j++) {
				int xlim = (i & 2 ? j : (N - 1) - j);
				int ylim = (i & 1 ? P[j] : (N - 1) - P[j]);
				if (dp[i][j] > min(xlim, ylim)) {
					dp[i][j] = INF;
				}
			}
		}
		if (dp == vector<vector<int> >(4, vector<int>(N, INF))) {
			break;
		}
		t += 1;
	}
	return N - t;
}

int main() {
	int N;
	cin >> N;
	vector<int> P(N);
	for (int i = 0; i < N; i++) {
		cin >> P[i];
		P[i] -= 1;
	}
	int answer = solve(N, P);
	cout << answer << endl;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 41 / 41