oj.uz

Submission #198275

# Submission time Handle Problem Language Result Execution time Memory
198275 2020-01-25T11:20:00 Z dennisstar Dancing Elephants (IOI11_elephants) C++17
26 / 100
 21 ms 1528 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 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct

Subtask #3
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 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Incorrect 21 ms 1528 KB Output isn't correct
8 Halted 0 ms 0 KB -

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 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Incorrect 21 ms 1528 KB Output isn't correct
8 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 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Incorrect 21 ms 1528 KB Output isn't correct
8 Halted 0 ms 0 KB -