Submission #285120

#	Time	Username	Problem	Language	Result	Execution time	Memory
285120		melon940925	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KiB

elephants

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, L, Q, sz = 400;
int B[440][440], cnt[440];
int C[440][440], P[440][440];
int A[161616], T[161616], num;

void con(int k) {
	int r = cnt[k];//k번째 버킷에 있는 코끼리의 수=r
	C[k][r] = 0;//해당 버킷의 인덱스 r=0
	for (int i = r - 1; i >= 0; i--) {
		while (B[k][r - 1] - B[k][i] > L) r--;
		C[k][i] = C[k][r] + 1;
		if (C[k][i] == 1) P[k][i] = B[k][i] + L;
		else P[k][i] = P[k][r];
	}
}

void reset() {
	for (int i = 0; i < N / sz; i++) cnt[i] = 0;
	//cnt배열 초기화
	for (int i = 0; i < N; i++) B[i / sz][cnt[i / sz]++] = T[i];
	//T[i]는 코끼리의 위치가 순서대로 들어있음
	//B는 bucket를 뜻함 
	//sz=400
	//i=0~400까지 cnt[0]이 증가함
	for (int i = 0; i < N / sz; i++) con(i);
	//각각의 바구니들에 대해 con실행
}

int main() {
	scanf("%d %d %d", &N, &L, &Q);//N은 코끼리의 갯수, L은 카메라의 길이, Q는 쿼리의 갯수
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);//A[i]는 i번 코끼리의 위치
		T[i] = A[i];//T[i]는 왼쪽에서 i번째 코끼리의 위치
	}
	reset();

	while (Q--) {
		int x, a, t = 0;
		scanf("%d %d", &x, &a);

		for (int i = 0; i <= (N - 1) / sz; i++) if (cnt[i] && B[i][0] <= A[x]) t = i;
		for (int i = 0; i < cnt[t]; i++) if (B[t][i] == A[x]) swap(B[t][i], B[t][i + 1]);
		cnt[t]--;
		con(t);

		A[x] = a, t = 0;
		for (int i = 0; i <= (N - 1) / sz; i++) if (cnt[i] && B[i][0] <= a) t = i;
		B[t][cnt[t]++] = a;
		for (int i = cnt[t] - 1; i > 0; i--) if (B[t][i] < B[t][i - 1]) swap(B[t][i], B[t][i - 1]);
		con(t);

		int p = -1, ans = 0;
		for (int i = 0; i <= (N - 1) / sz; i++) {
			t = upper_bound(B[i], B[i] + cnt[i], p) - B[i];
			if (t == cnt[i]) continue;
			ans += C[i][t], p = P[i][t];
		}
		printf("%d\n", ans);

		if (Q % sz == 0) {
			num = 0;
			for (int i = 0; i <= (N - 1) / sz; i++) for (int k = 0; k < cnt[i]; k++) T[num++] = B[i][k];
			reset();
		}
	}
	return 0;
}

Compilation message (stderr)

elephants.cpp: In function 'int main()':
elephants.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d %d %d", &N, &L, &Q);//N은 코끼리의 갯수, L은 카메라의 길이, Q는 쿼리의 갯수
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |   scanf("%d", &A[i]);//A[i]는 i번 코끼리의 위치
      |   ~~~~~^~~~~~~~~~~~~
elephants.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   scanf("%d %d", &x, &a);
      |   ~~~~~^~~~~~~~~~~~~~~~~
/tmp/ccgLTTMR.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccaVyisG.o:elephants.cpp:(.text.startup+0x0): first defined here
/tmp/ccgLTTMR.o: In function `main':
grader.cpp:(.text.startup+0x18): undefined reference to `init(int, int, int*)'
grader.cpp:(.text.startup+0x3a): undefined reference to `update(int, int)'
collect2: error: ld returned 1 exit status