oj.uz

Submission #20694

# Submission time Handle Problem Language Result Execution time Memory
20694 2017-02-13T14:07:25 Z Namnamseo Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 23956 KB 
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>
#define BS 400
using namespace std;

int n;
int l;

struct buck {
	int pos[1010];
	int dp [1010];
	int ep [1010];
	int sz;
	buck(){ sz=0; }

	void recalcDP(int until){
		for(int i=until; 0<=i; --i){
			auto it=upper_bound(pos, pos+sz, pos[i]+l);

			if(it == pos+sz){
				dp[i] = 0;
				ep[i] = pos[i];
			} else {
				dp[i] = 1+dp[it-pos];
				ep[i] = ep[it-pos];
			}
		}
	}

	void ins(int x){
		if(sz == 0){
			pos[0] = x;
			dp [0] = 0;
			ep [0] = x;
			sz = 1;
			return;
		}
		auto it=upper_bound(pos, pos+sz, x);
		if(it != pos+sz){
			rotate(it, pos+sz, pos+sz+1);
			rotate(dp+(it-pos), dp+sz, dp+sz+1);
			rotate(ep+(it-pos), ep+sz, ep+sz+1);
		}
		*it = x;
		++sz;

		recalcDP(it-pos);
	}

	void rem(int x){
		int p = lower_bound(pos, pos+sz, x)-pos;
		rotate(pos+p, pos+p+1, pos+sz);
		rotate(dp +p, dp +p+1, dp +sz);
		rotate(ep +p, ep +p+1, ep +sz);
		--sz;

		if(sz) recalcDP(min(sz-1,p));
	}
} bucks[510];
int bn;

int findBuck(int x){
	if(x < bucks[0].pos[0]) return 0;
	for(int i=0; i<bn; ++i){
		if(bucks[i].pos[0]<=x && (i==bn-1 || x<bucks[i+1].pos[0])) return i;
	}
    for(;;);
	return -1;
}

int sqrtN;

int pos   [150001];
int sorted[150001];

void recreateBuck(bool init){
	if(init){
		memcpy(sorted, pos, n*sizeof(int));
	} else {
		int ind = 0;
		for(int i=0; i<bn; ++i){
			int *arr = bucks[i].pos;
			int sz=bucks[i].sz;
			for(int j=0; j<sz; ++j){
				sorted[ind++] = arr[j];
			}
			bucks[i].sz = 0;
		}
	}

	bn = 0;
	for(int i=0; i<n; ++i){
		int cb=i/BS;
		if(cb >= bn) ++bn;
		int& sz=bucks[cb].sz;
		bucks[cb].pos[sz++] = sorted[i];
	}
	for(int i=0; i<bn; ++i){
		bucks[i].recalcDP(bucks[i].sz-1);
	}
}

void init(int N, int L, int X[])
{
	n = N; l = L;

	for(int i=0; i<n; ++i) pos[i] = X[i];

	recreateBuck(1);
}

int timer = 0;

int getAns(){
	int lastP = bucks[0].ep[0];
	int ans = bucks[0].dp[0];

	for(int i=1; i<bn; ++i){
		if(lastP + l >= bucks[i].pos[bucks[i].sz-1]) continue;
		++ans;
		int ind = upper_bound(bucks[i].pos, bucks[i].pos+bucks[i].sz, lastP+l)-bucks[i].pos;
		ans += bucks[i].dp[ind];
		lastP = bucks[i].ep[ind];
	}
	++ans;
	return ans;
}

int update(int i, int y)
{
	int t = findBuck(pos[i]);
	int nt = findBuck(y);
	bucks[t].rem(pos[i]);

	pos[i]=y;

	bucks[nt].ins(y);

	++timer;
	if(timer >= BS){
		recreateBuck(0);
		timer = 0;
	}
	return getAns();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 23956 KB Output is correct
2 Correct 949 ms 23956 KB Output is correct
3 Correct 1299 ms 23956 KB Output is correct
4 Correct 1859 ms 23956 KB Output is correct
5 Correct 1886 ms 23956 KB Output is correct
6 Correct 1509 ms 23956 KB Output is correct
7 Correct 1816 ms 23956 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 23956 KB Output is correct
2 Correct 1446 ms 23956 KB Output is correct
3 Correct 2069 ms 23956 KB Output is correct
4 Correct 2429 ms 23956 KB Output is correct
5 Correct 2396 ms 23956 KB Output is correct
6 Correct 1296 ms 23956 KB Output is correct
7 Correct 2499 ms 23956 KB Output is correct
8 Correct 2366 ms 23956 KB Output is correct
9 Correct 2753 ms 23956 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7816 ms 23956 KB Output is correct
2 Correct 8086 ms 23956 KB Output is correct
3 Correct 7103 ms 23956 KB Output is correct
4 Execution timed out 9000 ms 23956 KB Execution timed out
5 Halted 0 ms 0 KB -