제출 #353342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
353342		Kevin_Zhang_TW	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	100 / 100	3917 ms	7532 KiB

elephants

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
const int MAX_N = 1000010;

#include "elephants.h"
#ifdef KEV
#include "grader.cpp"
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T, class ...U> void kout (T v, U ...e) { cerr << v << ' ', kout(e...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !

const int SQ = 512, BSQ = SQ << 1;

int n, loc[MAX_N], sorted[MAX_N], Lim, blen;

struct bucket {
	int xs[BSQ], need[BSQ], ed[BSQ], sz;
	int minval() { return xs[0]; }
	int maxval() { return xs[sz-1]; }
	bool contain(int x) { return minval() <= x && x <= maxval(); }
	void clear() { sz = 0; }
	// they're sorted already
	void init(int l, int r) { 
		copy(sorted + l, sorted + r, xs);
		sz = r - l;
		rebuild();
	}
	void resorted(int &pos) {
		for (int i = 0;i < sz;++i)
			sorted[pos++] = xs[i];
	}
	bool smartpb(int x) { 
		xs[sz++] = x;
		int p = sz - 1;
		while (p && xs[p] < xs[p-1])
			swap(xs[p], xs[p-1]), --p;
		if (sz == BSQ) return true;
		rebuild();
		return false;
   	}
	// it has to exist
	bool smartrm(int x) {
		int p = 0;
		while (xs[p] < x) ++p;
		while (p + 1 < sz) xs[p] = xs[p+1], ++p;
		if (--sz == 0) return true;
		rebuild();
		return false;
	}
	// when rebuild, I have xs sorted already
	void rebuild() {
		for (int i = sz - 1, j = sz - 1;i >= 0;--i) {
			int R = xs[i] + Lim;
			while (j && xs[j - 1] > R) --j;
			if (R >= maxval()) 
				need[i] = 1, ed[i] = R;
			else
				need[i] = 1 + need[j], ed[i] = ed[j];
		}
	}
	void advance(int &R, int &cnt) {
		int p = upper_bound(xs, xs + sz, R) - xs;
		R = ed[p], cnt += need[p];
	}
	void out() { for (int i = 0;i < sz;++i) cerr << xs[i] << ' '; }
}buk[SQ];

void rebuildall() {
	int h = 0;
	for (int i = 0;i < blen;++i)
		buk[i].resorted(h);
	for (int id = 0;;++id) {
		int L = id * SQ, R = min(h, L + SQ);
		buk[id].init(L, R);
		blen = id + 1;
		if (R == h) break;
	}
}
void remove(int x) {
	for (int i = 0;i < blen;++i)
		if (buk[i].contain(x)) {
			if (buk[i].smartrm(x))
				rebuildall();
			break;
		}
}
void insert(int x) {
	for (int i = 0;i < blen;++i) {
		if (i == blen-1 || buk[i+1].minval() > x) {
			if (buk[i].smartpb(x))
				rebuildall();
			break;
		}
	}
}
int qry() {
	int curR = -1, res = 0;
	for (int i = 0;i < blen;++i) {
		if (curR >= buk[i].maxval()) continue;
		buk[i].advance(curR, res);
	}
	return res;
}

void init(int N, int L, int X[]) {
	n = N;
	Lim = L;
	copy(X, X+N, loc), copy(X, X+N, sorted);
	DE(N, Lim);
	for (int id = 0;;++id) {
		int L = id * SQ, R = min(n, L + SQ);
		buk[id].init(L, R);
		blen = id + 1;
		if (R == n) break;
	}
}

int update(int i, int y) {
	if (n == 1) return 1;
	remove(loc[i]);
	insert(loc[i] = y);
	return qry();
}

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

elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
elephants.cpp:124:2: note: in expansion of macro 'DE'
  124 |  DE(N, Lim);
      |  ^~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3