oj.uz

Submission #198276

# Submission time Handle Problem Language Result Execution time Memory
198276 2020-01-25T11:20:20 Z dennisstar Dancing Elephants (IOI11_elephants) C++17
50 / 100
 2486 ms 2936 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 1831 ms 1456 KB Output is correct
8 Correct 1875 ms 1628 KB Output is correct
9 Correct 2190 ms 2808 KB Output is correct
10 Correct 2051 ms 2936 KB Output is correct
11 Correct 1841 ms 2908 KB Output is correct
12 Correct 2486 ms 2816 KB Output is correct
13 Correct 1918 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 1831 ms 1456 KB Output is correct
8 Correct 1875 ms 1628 KB Output is correct
9 Correct 2190 ms 2808 KB Output is correct
10 Correct 2051 ms 2936 KB Output is correct
11 Correct 1841 ms 2908 KB Output is correct
12 Correct 2486 ms 2816 KB Output is correct
13 Correct 1918 ms 2808 KB Output is correct
14 Incorrect 506 ms 1976 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 1831 ms 1456 KB Output is correct
8 Correct 1875 ms 1628 KB Output is correct
9 Correct 2190 ms 2808 KB Output is correct
10 Correct 2051 ms 2936 KB Output is correct
11 Correct 1841 ms 2908 KB Output is correct
12 Correct 2486 ms 2816 KB Output is correct
13 Correct 1918 ms 2808 KB Output is correct
14 Incorrect 506 ms 1976 KB Output isn't correct
15 Halted 0 ms 0 KB -