oj.uz

Submission #198281

# Submission time Handle Problem Language Result Execution time Memory
198281 2020-01-25T11:32:24 Z dennisstar Dancing Elephants (IOI11_elephants) C++17
50 / 100
 2489 ms 2816 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%399==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 1825 ms 1528 KB Output is correct
8 Correct 1866 ms 1624 KB Output is correct
9 Correct 2200 ms 2680 KB Output is correct
10 Correct 2059 ms 2812 KB Output is correct
11 Correct 1843 ms 2816 KB Output is correct
12 Correct 2489 ms 2808 KB Output is correct
13 Correct 1937 ms 2808 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 1825 ms 1528 KB Output is correct
8 Correct 1866 ms 1624 KB Output is correct
9 Correct 2200 ms 2680 KB Output is correct
10 Correct 2059 ms 2812 KB Output is correct
11 Correct 1843 ms 2816 KB Output is correct
12 Correct 2489 ms 2808 KB Output is correct
13 Correct 1937 ms 2808 KB Output is correct
14 Incorrect 514 ms 1864 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 1825 ms 1528 KB Output is correct
8 Correct 1866 ms 1624 KB Output is correct
9 Correct 2200 ms 2680 KB Output is correct
10 Correct 2059 ms 2812 KB Output is correct
11 Correct 1843 ms 2816 KB Output is correct
12 Correct 2489 ms 2808 KB Output is correct
13 Correct 1937 ms 2808 KB Output is correct
14 Incorrect 514 ms 1864 KB Output isn't correct
15 Halted 0 ms 0 KB -