oj.uz

답안 #103911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103911 2019-04-03T08:57:41 Z KCSC 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
26 / 100
 616 ms 4856 KB 
// 8.45
#ifndef HOME
	#include "elephants.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 = 0) {
		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

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:70:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  if (nr = 0) {
      ~~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 492 ms 2528 KB Output is correct
8 Correct 616 ms 2936 KB Output is correct
9 Correct 584 ms 4856 KB Output is correct
10 Incorrect 46 ms 4736 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 492 ms 2528 KB Output is correct
8 Correct 616 ms 2936 KB Output is correct
9 Correct 584 ms 4856 KB Output is correct
10 Incorrect 46 ms 4736 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 492 ms 2528 KB Output is correct
8 Correct 616 ms 2936 KB Output is correct
9 Correct 584 ms 4856 KB Output is correct
10 Incorrect 46 ms 4736 KB Output isn't correct
11 Halted 0 ms 0 KB -