oj.uz

Submission #104648

# Submission time Handle Problem Language Result Execution time Memory
104648 2019-04-08T13:48:40 Z figter001 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 17416 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 = 800,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;
		}
	}
	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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1860 ms 1872 KB Output is correct
8 Correct 1814 ms 1868 KB Output is correct
9 Correct 1999 ms 3432 KB Output is correct
10 Correct 1694 ms 3432 KB Output is correct
11 Correct 1573 ms 3432 KB Output is correct
12 Correct 2373 ms 3432 KB Output is correct
13 Correct 1771 ms 3432 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1860 ms 1872 KB Output is correct
8 Correct 1814 ms 1868 KB Output is correct
9 Correct 1999 ms 3432 KB Output is correct
10 Correct 1694 ms 3432 KB Output is correct
11 Correct 1573 ms 3432 KB Output is correct
12 Correct 2373 ms 3432 KB Output is correct
13 Correct 1771 ms 3432 KB Output is correct
14 Correct 2526 ms 2288 KB Output is correct
15 Correct 2726 ms 2404 KB Output is correct
16 Correct 3354 ms 3696 KB Output is correct
17 Correct 3446 ms 4772 KB Output is correct
18 Correct 3790 ms 4544 KB Output is correct
19 Correct 3010 ms 4652 KB Output is correct
20 Correct 3647 ms 4672 KB Output is correct
21 Correct 3785 ms 4552 KB Output is correct
22 Correct 2584 ms 4680 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1860 ms 1872 KB Output is correct
8 Correct 1814 ms 1868 KB Output is correct
9 Correct 1999 ms 3432 KB Output is correct
10 Correct 1694 ms 3432 KB Output is correct
11 Correct 1573 ms 3432 KB Output is correct
12 Correct 2373 ms 3432 KB Output is correct
13 Correct 1771 ms 3432 KB Output is correct
14 Correct 2526 ms 2288 KB Output is correct
15 Correct 2726 ms 2404 KB Output is correct
16 Correct 3354 ms 3696 KB Output is correct
17 Correct 3446 ms 4772 KB Output is correct
18 Correct 3790 ms 4544 KB Output is correct
19 Correct 3010 ms 4652 KB Output is correct
20 Correct 3647 ms 4672 KB Output is correct
21 Correct 3785 ms 4552 KB Output is correct
22 Correct 2584 ms 4680 KB Output is correct
23 Correct 7603 ms 9420 KB Output is correct
24 Correct 8034 ms 9320 KB Output is correct
25 Correct 7626 ms 9320 KB Output is correct
26 Correct 6715 ms 9296 KB Output is correct
27 Correct 8767 ms 9380 KB Output is correct
28 Correct 6350 ms 5400 KB Output is correct
29 Correct 6502 ms 5404 KB Output is correct
30 Correct 6315 ms 5496 KB Output is correct
31 Correct 6280 ms 5360 KB Output is correct
32 Correct 6553 ms 13928 KB Output is correct
33 Correct 6630 ms 13132 KB Output is correct
34 Correct 7408 ms 14056 KB Output is correct
35 Correct 7775 ms 17416 KB Output is correct
36 Correct 7923 ms 13900 KB Output is correct
37 Execution timed out 9067 ms 16904 KB Time limit exceeded
38 Halted 0 ms 0 KB -