제출 #627467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
627467		Noam527	송신탑 (IOI22_towers)	C++17	0 / 100	1974 ms	269636 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
const int OO = 0;
using namespace std;

const int MAXN = 100005;
const int K = 300;

struct info {
	int v[2];
	info() {}
	int& operator [](int i) {
		return v[i];
	}
};

struct leap_info {
	int i, c; // start index, count
	leap_info() {}
	leap_info(int index, int count) {
		i = index;
		c = count;
	}
	bool operator < (const leap_info &a) const {
		return i < a.i;
	}
};

int n;
vector<int> h;
int d;
vector<info> to;

vector<leap_info> leap_to[MAXN / K + 2][K + 2][2];

void init(int N, std::vector<int> H) {
	d = -1;
	n = N;
	h = H;
	to.resize(n);
}

void real_init() {
	if (OO) {
		cout << "begin real_init\n";
	}
	// prepare edges
	vector<int> upper, lower;
	for (int i = n - 1; i >= 0; i--) {
		while (upper.size() && h[i] > h[upper.back()]) upper.pop_back();
		upper.push_back(i);
		while (lower.size() && h[i] < h[lower.back()]) lower.pop_back();
		lower.push_back(i);

		int lo, hi, mid;

		lo = -1, hi = (int)upper.size() - 1;
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (h[i] + d <= h[upper[mid]]) lo = mid;
			else hi = mid - 1;
		}
		if (lo == -1) to[i][0] = n;
		else to[i][0] = upper[lo];
		
		lo = -1, hi = (int)lower.size() - 1;
		while (lo < hi) {
			mid = (lo + hi + 1) / 2;
			if (h[i] - d >= h[lower[mid]]) lo = mid;
			else hi = mid - 1;
		}
		if (lo == -1) to[i][1] = n;
		else to[i][1] = lower[lo];
	}
	if (OO) {
		cout << "finished upper lower:\n";
		cout << "0:\n";
		for (auto &i : to) cout << i[0] << " "; cout << '\n';
		cout << "1:\n";
		for (auto &i : to) cout << i[1] << " "; cout << '\n';
	}
	// prepare leaps
	for (int chunk = 1; chunk * K < n; chunk++) {
		int lim = chunk * K; // [lim, inf) -> [0, K]
		vector<info> index(lim), count(lim);
		for (int i = lim - 1; i >= 0; i--) {
			int last_layer;
			if (to[i][0] >= lim) {
				index[i][0] = min(to[i][0], lim + K);
				count[i][0] = 1;
			}
			else {
				index[i][0] = index[to[i][0]][1];
				count[i][0] = 1 + count[to[i][0]][1];
			}
			last_layer = (0 + count[i][0]) % 2;
			leap_to[chunk][index[i][0] - lim][last_layer].emplace_back(i, count[i][0]);
			if (to[i][1] >= lim) {
				index[i][1] = min(to[i][1], lim + K);
				count[i][1] = 1;
			}
			else {
				index[i][1] = index[to[i][1]][0];
				count[i][1] = 1 + count[to[i][1]][0];
			}
			last_layer = (1 + count[i][1]) % 2;
			leap_to[chunk][index[i][1] - lim][last_layer].emplace_back(i, count[i][1]);
		}
		for (int res = 0; res <= K; res++) for (int b = 0; b <= 1; b++) {
			for (int i = 1; i < leap_to[chunk][res][b].size(); i++)
				if (leap_to[chunk][res][b][i].c < leap_to[chunk][res][b][i - 1].c)
					leap_to[chunk][res][b][i].c = leap_to[chunk][res][b][i - 1].c;
			reverse(leap_to[chunk][res][b].begin(), leap_to[chunk][res][b].end());
		}
	}
	if (OO) {
		cout << "end real_init\n";
	}
}

int max_towers(int L, int R, int D) {
	if (d == -1) {
		d = D;
		real_init();
	}
	int chunk = R / K;
	int lim = chunk * K;
	
	int result = 1;
	vector<info> count(R - lim + 1);
	for (int i = R; i >= lim && i >= L; i--) {
		int placei = i - lim;
		if (to[i][0] > R)
			count[placei][0] = 1;
		else
			count[placei][0] = max(1, 1 + count[to[i][0] - lim][1]);
		if (to[i][1] > R)
			count[placei][1] = -1e9; // NOTE: we must end on a minimum
		else
			count[placei][1] = max(1, 1 + count[to[i][1] - lim][0]);

		if (chunk == 0) {
			result = max(max(result, count[placei][0]), count[placei][1]);
		}
		else {
			// ends at 0: leap_to[chunk][placei][0]
			auto it = lower_bound(leap_to[chunk][placei][0].begin(), leap_to[chunk][placei][0].end(), leap_info(L, 0));
			if (it != leap_to[chunk][placei][0].end())
				result = max(result, max(0, count[placei][0]) + it->c);
			// ends at 1: leap_to[chunk][placei][1]
			it = lower_bound(leap_to[chunk][placei][1].begin(), leap_to[chunk][placei][1].end(), leap_info(L, 0));
			if (it != leap_to[chunk][placei][1].end())
				result = max(result, max(0, count[placei][1]) + it->c);
		}
	}
	if (chunk > 0) {
		// also check stuff that exceed R: [R - lim + 1, K]
		// make sure we exceed with a maximum
		for (int res = R - lim + 1; res <= K; res++) {
			auto it = lower_bound(leap_to[chunk][res][1].begin(), leap_to[chunk][res][1].end(), leap_info(L, 0));
			if (it != leap_to[chunk][res][1].end())
				result = max(result, it->c);
		}
	}
	if (OO) {
		cout << "result " << result << '\n';
	}
	return (result + 1) / 2;
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In function 'void real_init()':
towers.cpp:78:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |   for (auto &i : to) cout << i[0] << " "; cout << '\n';
      |   ^~~
towers.cpp:78:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |   for (auto &i : to) cout << i[0] << " "; cout << '\n';
      |                                           ^~~~
towers.cpp:80:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   80 |   for (auto &i : to) cout << i[1] << " "; cout << '\n';
      |   ^~~
towers.cpp:80:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |   for (auto &i : to) cout << i[1] << " "; cout << '\n';
      |                                           ^~~~
towers.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<leap_info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    for (int i = 1; i < leap_to[chunk][res][b].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23