Submission #358999

#	Time	Username	Problem	Language	Result	Execution time	Memory
358999		hivakarami	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	24 ms	2540 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
 
const int N = 15e4 + 100;
const int sq = 500;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
 
int n, len, q = 0, m = 0;
int id[N];
int *a;
vector<int> v[sq], tmp;
int nx[sq][N], dp[sq][N];
//*
void init(int N, int L, int X[])
{
	n = N;
	len = L;
	a = X;
}
//*/
 
void bld(int x)
{
	int sz = v[x].size();
	int pt = sz;
	for(int i = sz - 1; i >= 0; i--)
	{
		while(pt > 0 && v[x][pt-1] > v[x][i] + len)
			pt--;
		if(pt >= sz)
		{
			dp[x][i] = 1;
			nx[x][i] = v[x][i] + len + 1;
		}
		else
		{
			dp[x][i] = dp[x][pt] + 1;
			nx[x][i] = nx[x][pt];
		}
	}
}
 
 
void build()
{
	vector<pair<int, int>> vec;

	for(int i = 0; i < m; i++)
		v[i].clear();
 
	for(int i = 0; i < n; i++)
		vec.push_back({a[i], i});
	sort(vec.begin(), vec.end());	
		
		
	m = 0;
	for(int i = 0; i < n; i++)
	{
		if(v[m].size() == sq)
			bld(m++);
		v[m].push_back(vec[i].f);
		id[vec[i].s] = m;
	}
	
	bld(m++);
}
 
 
 
 
void del(int i)
{
	tmp.clear();
	int j = id[i];
	bool fl = true;
	for(auto x : v[j])
	{
		if(fl && x == a[i])
			fl = false;
		else
			tmp.push_back(x);
	} 	
	v[j] = tmp;
	
	bld(j);
}
 
 

void add(int i, int y)
{

	//cout << "add" << ' ' << i << ' ' << y << endl;

	tmp.clear();
	int j = 0;
	while(j+1 < m && v[j+1][0] > y)
		j++;
	bool fl = false;
	for(auto x : v[j])
	{
		if(!fl && x > y)
		{
			tmp.push_back(y);
			fl = true;
		}
		tmp.push_back(x);
	}	
	if(!fl)
		tmp.push_back(y);
	
	v[j] = tmp;		
	
	a[i] = y;
	id[i] = j;
	
	bld(j);
		
		
} 

int get_ans()
{
	int res = 0, pt = 0, c = v[0][0];
	while(pt < m)
	{
		while(pt < m && v[pt].back() < c)
			pt++;
		if(pt >= m)
			break;
		
		int k = lower_bound(v[pt].begin(), v[pt].end(), c) - v[pt].begin();
		res += dp[pt][k];
		c = nx[pt][k];
		
	}
	return res;
}


 
 
int update(int i, int y)
{
	if(q%(sq-2) == 0)
		build();
	q++;
	
	del(i);
	add(i, y);
	
	return get_ans();
	
}
 
/*
int main()
{
	cin >> n >> len;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	
	int qu;
	cin >> qu;
	while(qu--)
	{
		int a, b;
		cin >> a >> b;
		//cout << "///////////" << endl;
		cout << update(a, b) << '\n';
		
		for(int i = 0; i < m; i++)
		{
			for(auto x : v[i])
				cout << x << ' ';
			cout << endl;
		}
		
	}
	
	return 0;
		
}
//*/

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3