oj.uz

Submission #104646

# Submission time Handle Problem Language Result Execution time Memory
104646 2019-04-08T13:46:16 Z figter001 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 8908 KB 
// #include "grader.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int nax = 2e5;
const int bax = 400;

int n,l,Z = 1005,cnt;
vector<pair<int,int>> a;
int p[nax],id[nax];

struct node{
	int val,id,nxt,cnt;
};
vector<node> b[bax];

void build(){
	vector<pair<int,int>> a = ::a;
	sort(a.begin(),a.end());
	int at = -1;
	int to = (n+Z-1)/Z;
	for(int i=0;i<to;i++)
		b[i].clear();
	for(int i=0;i<n;i++){
		int cur = a[i].first;
		while(at < i && cur - a[at+1].first > l)
			at++;
		id[a[i].second] = i/Z;
		if(at == -1 || at/Z != i/Z)
			b[i/Z].push_back({cur,a[i].second,cur - l,1});
		else
			b[i/Z].push_back({cur,a[i].second,b[at/Z][at%Z].nxt,b[at/Z][at%Z].cnt + 1});
	}
}

void rem(int bucket,int val){
	vector<pair<int,int>> tmp;
	for(int i=0;i<b[bucket].size();i++){
		if(b[bucket][i].id == val)
			continue;
		tmp.push_back({b[bucket][i].val,b[bucket][i].id});
	}
	b[bucket].clear();
	int at = -1;
	for(int i=0;i<tmp.size();i++){
		int cur = tmp[i].first;
		while(at < i && cur - tmp[at+1].first > l)
			at++;
		if(at == -1)
			b[bucket].push_back({cur,tmp[i].second,cur - l,1});
		else
			b[bucket].push_back({cur,tmp[i].second,b[bucket][at].nxt,b[bucket][at].cnt + 1});
	}
}

void add(int val,int x){
	int to = (n+Z-1)/Z;
	int bucket = to - 1;
	for(int i=0;i<to;i++){
		if(b[i].size() && val <= b[i].back().val){
			bucket = i;
			break;
		}
	}
	id[x] = bucket;
	vector<pair<int,int>> tmp;
	bool ad = 0;
	for(int i=0;i<b[bucket].size();i++){
		if(b[bucket][i].val >= val && !ad){
			tmp.push_back({val,x});
			ad = 1;
		}
		tmp.push_back({b[bucket][i].val,b[bucket][i].id});
	}
	if(!ad)
		tmp.push_back({val,x});
	b[bucket].clear();
	int at = -1;
	for(int i=0;i<tmp.size();i++){
		int cur = tmp[i].first;
		while(at < i && cur - tmp[at+1].first > l)
			at++;
		if(at == -1)
			b[bucket].push_back({cur,tmp[i].second,cur - l,1});
		else
			b[bucket].push_back({cur,tmp[i].second,b[bucket][at].nxt,b[bucket][at].cnt + 1});
	}
}

void init(int N, int L, int X[]){
	n = N;
	// Z = sqrt(n) + 1;
	l=L;
	for(int i=0;i<n;i++){
		a.push_back({X[i],i});
		p[i] = X[i];
	}
	build();
}

int update(int x, int y){
	if(cnt == Z - 2){
		build();
		cnt = 0;
	}
	cnt++;
	int curbucket = id[x];
	a[x].first = y;
	rem(curbucket,x);
	add(y,x);

	int ans = 0;

	int cur = (n+Z-1)/Z - 1;
	while(cur >= 0 && b[cur].size() == 0)
		cur--;
	int at = b[cur].size() - 1;

	for(int i=cur;i>=0;i--){
		ans += b[i][at].cnt;
		int to = b[i][at].nxt;
		if(i == 0)
			break;
		while(1){
			if(i == 0)
				break;
			int small = (int)2e9;
			if(b[i-1].size())
				small = b[i-1][0].val;
			if(small >= to)
				i--;
			else
				break;
		}
		if(i == 0)
			break;
		int md,lo=0,hi=b[i-1].size()-1;
		at = -1;
		while(lo <= hi){
			md = (lo + hi)/2;
			if(b[i-1][md].val < to){
				lo = md+1;
				at = md;
			}else hi = md-1;
		}
		assert(at!=-1);
	}
	return ans;
}

Compilation message

elephants.cpp: In function 'void rem(int, int)':
elephants.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b[bucket].size();i++){
              ~^~~~~~~~~~~~~~~~~
elephants.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
              ~^~~~~~~~~~~
elephants.cpp: In function 'void add(int, int)':
elephants.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b[bucket].size();i++){
              ~^~~~~~~~~~~~~~~~~
elephants.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
              ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2183 ms 1956 KB Output is correct
8 Correct 2293 ms 2152 KB Output is correct
9 Correct 2249 ms 3312 KB Output is correct
10 Correct 2314 ms 3436 KB Output is correct
11 Correct 2119 ms 3312 KB Output is correct
12 Correct 2712 ms 3836 KB Output is correct
13 Correct 2307 ms 3540 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2183 ms 1956 KB Output is correct
8 Correct 2293 ms 2152 KB Output is correct
9 Correct 2249 ms 3312 KB Output is correct
10 Correct 2314 ms 3436 KB Output is correct
11 Correct 2119 ms 3312 KB Output is correct
12 Correct 2712 ms 3836 KB Output is correct
13 Correct 2307 ms 3540 KB Output is correct
14 Correct 3040 ms 2504 KB Output is correct
15 Correct 3222 ms 2472 KB Output is correct
16 Correct 4156 ms 3744 KB Output is correct
17 Correct 4103 ms 4840 KB Output is correct
18 Correct 4339 ms 4968 KB Output is correct
19 Correct 3624 ms 4672 KB Output is correct
20 Correct 4256 ms 4748 KB Output is correct
21 Correct 4222 ms 4904 KB Output is correct
22 Correct 3200 ms 4424 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2183 ms 1956 KB Output is correct
8 Correct 2293 ms 2152 KB Output is correct
9 Correct 2249 ms 3312 KB Output is correct
10 Correct 2314 ms 3436 KB Output is correct
11 Correct 2119 ms 3312 KB Output is correct
12 Correct 2712 ms 3836 KB Output is correct
13 Correct 2307 ms 3540 KB Output is correct
14 Correct 3040 ms 2504 KB Output is correct
15 Correct 3222 ms 2472 KB Output is correct
16 Correct 4156 ms 3744 KB Output is correct
17 Correct 4103 ms 4840 KB Output is correct
18 Correct 4339 ms 4968 KB Output is correct
19 Correct 3624 ms 4672 KB Output is correct
20 Correct 4256 ms 4748 KB Output is correct
21 Correct 4222 ms 4904 KB Output is correct
22 Correct 3200 ms 4424 KB Output is correct
23 Correct 8596 ms 8900 KB Output is correct
24 Correct 8800 ms 8908 KB Output is correct
25 Correct 7910 ms 8860 KB Output is correct
26 Correct 6834 ms 8812 KB Output is correct
27 Execution timed out 9062 ms 8808 KB Time limit exceeded
28 Halted 0 ms 0 KB -