oj.uz

Submission #359026

# Submission time Handle Problem Language Result Execution time Memory
359026 2021-01-26T09:15:38 Z hivakarami Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8625 ms 18208 KB 
#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[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)
{
	//cout << "del" << ' ' << i << endl;
	
	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 << update(a, b) << '\n';
		
	}
	
	return 0;
	
	4 10
	10 15 17 20
	5
	2 16
	1 25
	3 35
	0 38
	2 0
		
}
//*/

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 746 ms 2696 KB Output is correct
8 Correct 784 ms 3148 KB Output is correct
9 Correct 831 ms 5664 KB Output is correct
10 Correct 898 ms 5328 KB Output is correct
11 Correct 927 ms 5332 KB Output is correct
12 Correct 1310 ms 5624 KB Output is correct
13 Correct 930 ms 5240 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 746 ms 2696 KB Output is correct
8 Correct 784 ms 3148 KB Output is correct
9 Correct 831 ms 5664 KB Output is correct
10 Correct 898 ms 5328 KB Output is correct
11 Correct 927 ms 5332 KB Output is correct
12 Correct 1310 ms 5624 KB Output is correct
13 Correct 930 ms 5240 KB Output is correct
14 Correct 824 ms 4124 KB Output is correct
15 Correct 1178 ms 4232 KB Output is correct
16 Correct 1977 ms 6260 KB Output is correct
17 Correct 2232 ms 7836 KB Output is correct
18 Correct 2374 ms 7684 KB Output is correct
19 Correct 1569 ms 8264 KB Output is correct
20 Correct 2277 ms 7988 KB Output is correct
21 Correct 2216 ms 8028 KB Output is correct
22 Correct 1568 ms 7512 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 746 ms 2696 KB Output is correct
8 Correct 784 ms 3148 KB Output is correct
9 Correct 831 ms 5664 KB Output is correct
10 Correct 898 ms 5328 KB Output is correct
11 Correct 927 ms 5332 KB Output is correct
12 Correct 1310 ms 5624 KB Output is correct
13 Correct 930 ms 5240 KB Output is correct
14 Correct 824 ms 4124 KB Output is correct
15 Correct 1178 ms 4232 KB Output is correct
16 Correct 1977 ms 6260 KB Output is correct
17 Correct 2232 ms 7836 KB Output is correct
18 Correct 2374 ms 7684 KB Output is correct
19 Correct 1569 ms 8264 KB Output is correct
20 Correct 2277 ms 7988 KB Output is correct
21 Correct 2216 ms 8028 KB Output is correct
22 Correct 1568 ms 7512 KB Output is correct
23 Correct 5666 ms 16668 KB Output is correct
24 Correct 6029 ms 16752 KB Output is correct
25 Correct 5208 ms 16568 KB Output is correct
26 Correct 6958 ms 16940 KB Output is correct
27 Correct 7191 ms 16848 KB Output is correct
28 Correct 2496 ms 5512 KB Output is correct
29 Correct 2457 ms 5356 KB Output is correct
30 Correct 2551 ms 5484 KB Output is correct
31 Correct 2430 ms 5612 KB Output is correct
32 Correct 5771 ms 16312 KB Output is correct
33 Correct 5572 ms 15360 KB Output is correct
34 Correct 6071 ms 16372 KB Output is correct
35 Correct 5527 ms 18208 KB Output is correct
36 Correct 3944 ms 16200 KB Output is correct
37 Correct 8625 ms 17484 KB Output is correct
38 Correct 6108 ms 15388 KB Output is correct
39 Correct 6268 ms 16448 KB Output is correct
40 Correct 6428 ms 15380 KB Output is correct
41 Correct 8595 ms 16096 KB Output is correct
42 Correct 8612 ms 16148 KB Output is correct