oj.uz

답안 #104643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104643 2019-04-08T13:29:22 Z figter001 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
10 / 100
 3 ms 384 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,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;
		// cout << cur << ' ' << a[i].second << endl;
		if(at == -1 || a[at].first/Z != cur/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});
	}
	// for(auto v : b[bucket])
	// 	cout << v.val << ' ';
	// printf("\n");
}

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;
	// cout << x << ' ' << val << ' ' << bucket << endl;
	// for(auto v : b[bucket])
	// 	cout << v.val << ' ';
	// printf("\n");
	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});
	// for(auto v : tmp)
	// 	cout << v.first << ' ';
	// printf("\n");
	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});
	}
	// for(auto v : b[bucket])
	// 	cout << v.val << ' ';
	// printf("\n");
}

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];
	}
}

int update(int x, int y){
	if(cnt % Z == 0)
		build();
	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;
	// for(int i=0;i<=cur;i++){
	// 	cout << i << endl;
	// 	for(node v : b[i])
	// 		cout << v.val << ' ';
	// 	printf("\n");
	// }
	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;
		// cout << i << ' ' << at << ' ' << b[i][at].val << ' ' << b[i][at].cnt << ' ' << to << endl;
		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);
	}
	// printf("\n");
	return ans;
}

Compilation message

elephants.cpp: In function 'void rem(int, int)':
elephants.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b[bucket].size();i++){
              ~^~~~~~~~~~~~~~~~~
elephants.cpp:49: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:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b[bucket].size();i++){
              ~^~~~~~~~~~~~~~~~~
elephants.cpp:93: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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -