oj.uz

Submission #198274

# Submission time Handle Problem Language Result Execution time Memory
198274 2020-01-25T11:18:18 Z dennisstar Dancing Elephants (IOI11_elephants) C++17
50 / 100
 2487 ms 4340 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int N, L, X[150010], im[150010], Q;
int A[410][810], sz[410];
int B[410][810], C[410][810];

void myinit() {
	for (int i=0, k=0; i<=N/400; i++) for (int j=0; j<sz[i]; j++) im[k++]=A[i][j];
	memset(sz, 0, sizeof(sz));
	for (int i=0; i<N; i++) A[i/400][sz[i/400]++]=im[i];
	for (int i=0; i<=N/400; i++) for (int j=sz[i]-1; j>=0; j--) {
		int ub=upper_bound(A[i], A[i]+sz[i], A[i][j]+L)-A[i];
		if (ub>=sz[i]) B[i][j]=A[i][j], C[i][j]=1;
		else B[i][j]=B[i][ub], C[i][j]=C[i][ub]+1;
	}
}

void init(int N_, int L_, int X_[]) {
	N=N_; L=L_; for (int i=0; i<N; i++) { X[i]=X_[i]; A[i/400][sz[i/400]++]=X[i]; }
	for (int i=0; ; i++) if (!sz[i]) { A[i][0]=(1<<30); break; }
	myinit();
}

void del(int I, int J) {
	for (int i=J+1; i<sz[I]; i++) A[I][i-1]=A[I][i];
	sz[I]--;
	for (int i=sz[I]-1; i>=0; i--) {
		int ub=upper_bound(A[I], A[I]+sz[I], A[I][i]+L)-A[I];
		if (ub>=sz[I]) B[I][i]=A[I][i], C[I][i]=1;
		else B[I][i]=B[I][ub], C[I][i]=C[I][ub]+1;
	}
}

void ins(int I, int V) {
	int k; for (k=sz[I]-1; k>=0; k--) {
		if (A[I][k]<=V) { A[I][k+1]=V; break; }
		A[I][k+1]=A[I][k];
	}
	if (k<0) A[I][0]=V;
	sz[I]++;
	for (int i=sz[I]-1; i>=0; i--) {
		int ub=upper_bound(A[I], A[I]+sz[I], A[I][i]+L)-A[I];
		if (ub>=sz[I]) B[I][i]=A[I][i], C[I][i]=1;
		else B[I][i]=B[I][ub], C[I][i]=C[I][ub]+1;
	}
}

int update(int I, int Y) {
	Q++;
	if (Q%400==0) myinit();
	for (int i=0; i<=N/400; i++) if (sz[i] && X[I]<A[i+1][0]) {
		del(i, lower_bound(A[i], A[i]+sz[i], X[I])-A[i]);
		break;
	}
	for (int i=0; i<=N/400; i++) if (sz[i] && Y<A[i+1][0]) {
		ins(i, Y);
		break;
	}
	X[I]=Y;
	int lst=-L-10, ans=0;
	for (int i=0; i<=N/400; i++) if (sz[i]) {
		int ub=upper_bound(A[i], A[i]+sz[i], lst+L)-A[i];
		if (ub>=sz[i]) continue;
		ans+=C[i][ub]; lst=B[i][ub];
	}
	return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1826 ms 2356 KB Output is correct
8 Correct 1871 ms 2652 KB Output is correct
9 Correct 2197 ms 4340 KB Output is correct
10 Correct 2060 ms 4120 KB Output is correct
11 Correct 1842 ms 4088 KB Output is correct
12 Correct 2487 ms 4088 KB Output is correct
13 Correct 1925 ms 3904 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1826 ms 2356 KB Output is correct
8 Correct 1871 ms 2652 KB Output is correct
9 Correct 2197 ms 4340 KB Output is correct
10 Correct 2060 ms 4120 KB Output is correct
11 Correct 1842 ms 4088 KB Output is correct
12 Correct 2487 ms 4088 KB Output is correct
13 Correct 1925 ms 3904 KB Output is correct
14 Incorrect 410 ms 3360 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1826 ms 2356 KB Output is correct
8 Correct 1871 ms 2652 KB Output is correct
9 Correct 2197 ms 4340 KB Output is correct
10 Correct 2060 ms 4120 KB Output is correct
11 Correct 1842 ms 4088 KB Output is correct
12 Correct 2487 ms 4088 KB Output is correct
13 Correct 1925 ms 3904 KB Output is correct
14 Incorrect 410 ms 3360 KB Output isn't correct
15 Halted 0 ms 0 KB -