제출 #103914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103914		KCSC	Dancing Elephants (IOI11_elephants)	C++14	컴파일 에러	0 ms	0 KiB

elephants

// 8.45
#ifndef HOME
	#include "grader.h"
#endif
#include <bits/stdc++.h>
using namespace std;

	const int DIM = 160005;
	const int SQRT = 1005;
	const int INF = 1000000005;

int n, l;

pair<int, int> ele[DIM], iele[DIM];
vector<pair<int, int>> buc[DIM / SQRT];

int cnt[DIM / SQRT][SQRT * 2]; 
int nxt[DIM / SQRT][SQRT * 2], whb[DIM];

void updateDp(int b) {
	int s = (int) buc[b].size();
	for (int i = s - 1; i >= 1; --i) {
		if (buc[b][i - 1] > buc[b][i]) {
			swap(buc[b][i - 1], buc[b][i]); }
		else {
			break; } }	
	for (int i = 0; i < s; ++i) {
		whb[buc[b][i].second] = b; }
	for (int i = s - 1, j = s; i >= 0; --i) {
		while (buc[b][j - 1].first > buc[b][i].first + l) {
			--j; }
		if (j == s) {
			cnt[b][i] = 1; 
			nxt[b][i] = buc[b][i].first + l; }
		else {
			cnt[b][i] = 1 + cnt[b][j]; 
			nxt[b][i] = nxt[b][j]; } } }

void resetDp(void) {
	for (int i = 0; i < n; ++i) {
		ele[i] = iele[i]; }
	sort(ele, ele + n);
	for (int i = 0; i < n; ++i) {
		if (i % SQRT == 0) {
			buc[i / SQRT].clear(); }
		buc[i / SQRT].push_back(ele[i]); }
	for (int i = 0; i * SQRT < n; ++i) {
		updateDp(i); } }

void init(int _n, int _l, int *X) {
	n = _n; l = _l;
	for (int i = 0; i < n; ++i) {
		iele[i] = make_pair(X[i], i); }
	iele[n] = make_pair(-INF, n); ++n;
	while (n % SQRT != 0) {
		iele[n] = make_pair(-INF, n); ++n; }
	resetDp(); }

int query(void) {
	int ans = 0;
	for (int i = 0, v = -INF; i * SQRT < n; ++i) {
		if (prev(buc[i].end()) -> first < v) {
			continue; }
		auto it = lower_bound(buc[i].begin(), buc[i].end(), make_pair(v, 0)) - buc[i].begin();
		ans += cnt[i][it]; v = nxt[i][it] + 1; }
	return ans; }
	
int update(int x, int c) {
	static int nr = 0; 
	if (++nr == SQRT - 2) {
		iele[x].first = c; resetDp(); nr = 0; }
	else {
		int wb = whb[x], ps = iele[x].first; iele[x].first = c;
		buc[wb].erase(lower_bound(buc[wb].begin(), buc[wb].end(), make_pair(ps, x))); updateDp(wb);
		if (prev(buc[n / SQRT - 1].end()) -> first <= c) {
			buc[n / SQRT - 1].push_back(make_pair(c, x)); updateDp(n / SQRT - 1); }
		else {
			for (int i = 0; i * SQRT < n; ++i) {
				if (buc[i].begin() -> first <= c and (prev(buc[i].end()) -> first >= c or buc[i + 1].begin() -> first >= c)) {
					buc[i].push_back(make_pair(c, x)); updateDp(i); break; } } } }
	return query() - 1; }

#ifdef HOME
int main(void) {
	freopen("elephants.in", "r", stdin);
	freopen("elephants.out", "w", stdout);
	int N, L, M; cin >> N >> L >> M;
	int *X = new int[N];
	for (int i = 0; i < N; ++i) {
		cin >> X[i]; }
	init(N, L, X); int h = 0;
	while (M--) {
		int x, y, v; cin >> x >> y >> v; ++h;
		int u = update(x, y);
		if (update(x, y) != v) {	
			cout << h << " " << u << " " << v; return 0; } }
	cout << "True"; 
	return 0; }
#endif

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

elephants.cpp:3:11: fatal error: grader.h: No such file or directory
  #include "grader.h"
           ^~~~~~~~~~
compilation terminated.