oj.uz

Submission #225310

# Submission time Handle Problem Language Result Execution time Memory
225310 2020-04-20T09:08:38 Z davitmarg Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 25620 KB 
/*DavitMarg*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;


#ifndef death
#include "elephants.h"
#endif

const int N = 150005;
int K;


int n, len;
vector<pair<int, int>> dp[N], block[N], x;
vector<int> ps[N];
pair<int, int> pos[N];

void build(int i)
{
	//sort(all(block[i]));
	for (int j = 0; j < block[i].size(); j++)
		pos[block[i][j].second] = MP(i, j);
	dp[i].clear();
	dp[i].resize(block[i].size());

	ps[i].clear();
	ps[i].resize(block[i].size());
	int p = 0;

	for (int j = 0; j < block[i].size(); j++)
	{
		while (p < block[i].size() && block[i][p].first <= block[i][j].first + len)
			p++;
		ps[i][j] = p;
	}

	for (int j = block[i].size() - 1; j >= 0; j--)
	{
		if (block[i].back().first <= block[i][j].first + len)
		{
			dp[i][j] = MP(1, block[i][j].first + len);
			continue;
		}
		int pos = ps[i][j];
		dp[i][j] = MP(dp[i][pos].first + 1, dp[i][pos].second);
	}
}

void build()
{
	sort(all(x));
	for (int i = 0; i <= (n - 1) / K; i++)
		block[i].clear();
	for (int i = 0; i < n; i++)
	{
		block[i / K].push_back(x[i]);
		pos[x[i].second] = MP(i / K, i % K);
	}

	for (int i = 0; i <= (n - 1) / K; i++)
		build(i);

	sort(all(x), [](pair<int, int> a, pair<int, int> b) {
		return a.second < b.second;
	});
}

int get()
{
	int last = -mod;
	int ans = 0;
	for (int i = 0; i <= (n - 1) / K; i++)
	{
		if (block[i].back().first <= last)
			continue;
		int pos = upper_bound(all(block[i]), MP(last, n)) - block[i].begin();
		last = dp[i][pos].second;
		ans += dp[i][pos].first;
	}
	return ans;
}

int cnt = -1;

int update(int i, int nx)
{
	cnt++;
	if (cnt % K == 0)
	{
		x[i].first = nx;
		build();
		return get();
	}

	int bi = pos[i].first;

	for (int j = 0; j < block[bi].size() - 1; j++)
		if (block[bi][j] == x[i])
			swap(block[bi][j], block[bi][j + 1]);
	block[bi].pop_back();
	//build(bi);
	x[i].first = nx;

	bi = 0;
	for (int j = (n - 1) / K; j >= 0; j--)
	{
		if (!block[j].empty() && block[j][0].first <= nx)
		{
			bi = j;
			break;
		}
	}

	if (bi != pos[x[i].second].first)
		build(pos[x[i].second].first);

	block[bi].push_back(x[i]);
	for (int j = block[bi].size() - 1; j > 0; j--)
		if (block[bi][j] < block[bi][j - 1])
			swap(block[bi][j], block[bi][j - 1]);
	build(bi);

	return get();
}

void init(int N, int L, int X[])
{
	n = N;
	len = L;
	K = 700;
	for (int i = 0; i < n; i++)
		x.push_back(MP(X[i], i));
}

#ifdef death

int main()
{
	int n, len, x[N], q;
	cin >> n >> len;
	for (int i = 0; i < n; i++)
		cin >> x[i];
	init(n, len, x);

	cin >> q;
	while (q--)
	{
		int i, pos;
		cin >> i >> pos;
		cout << update(i, pos) << endl;
	}

	return 0;
}

#endif

/*

4 10
10 15 17 20
5
2 16
1 25
3 35
0 38
2 0


4 5
10 15 20 25
100
0 10
2 12
3 25




*/

Compilation message

elephants.cpp: In function 'void build(int)':
elephants.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < block[i].size(); j++)
                  ~~^~~~~~~~~~~~~~~~~
elephants.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < block[i].size(); j++)
                  ~~^~~~~~~~~~~~~~~~~
elephants.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (p < block[i].size() && block[i][p].first <= block[i][j].first + len)
          ~~^~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:122:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < block[bi].size() - 1; j++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10880 KB Output is correct
2 Correct 20 ms 10996 KB Output is correct
3 Correct 10 ms 11008 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10880 KB Output is correct
2 Correct 20 ms 10996 KB Output is correct
3 Correct 10 ms 11008 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 10932 KB Output is correct
6 Correct 12 ms 11060 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10880 KB Output is correct
2 Correct 20 ms 10996 KB Output is correct
3 Correct 10 ms 11008 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 10932 KB Output is correct
6 Correct 12 ms 11060 KB Output is correct
7 Correct 642 ms 13020 KB Output is correct
8 Correct 666 ms 13300 KB Output is correct
9 Correct 728 ms 15344 KB Output is correct
10 Correct 1044 ms 15088 KB Output is correct
11 Correct 1062 ms 14936 KB Output is correct
12 Correct 1853 ms 15352 KB Output is correct
13 Correct 952 ms 14832 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10880 KB Output is correct
2 Correct 20 ms 10996 KB Output is correct
3 Correct 10 ms 11008 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 10932 KB Output is correct
6 Correct 12 ms 11060 KB Output is correct
7 Correct 642 ms 13020 KB Output is correct
8 Correct 666 ms 13300 KB Output is correct
9 Correct 728 ms 15344 KB Output is correct
10 Correct 1044 ms 15088 KB Output is correct
11 Correct 1062 ms 14936 KB Output is correct
12 Correct 1853 ms 15352 KB Output is correct
13 Correct 952 ms 14832 KB Output is correct
14 Correct 1292 ms 14292 KB Output is correct
15 Correct 1032 ms 14300 KB Output is correct
16 Correct 2673 ms 16240 KB Output is correct
17 Correct 2894 ms 17048 KB Output is correct
18 Correct 3225 ms 16968 KB Output is correct
19 Correct 1981 ms 16876 KB Output is correct
20 Correct 2907 ms 17204 KB Output is correct
21 Correct 3086 ms 17028 KB Output is correct
22 Correct 1952 ms 16364 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10880 KB Output is correct
2 Correct 20 ms 10996 KB Output is correct
3 Correct 10 ms 11008 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 10932 KB Output is correct
6 Correct 12 ms 11060 KB Output is correct
7 Correct 642 ms 13020 KB Output is correct
8 Correct 666 ms 13300 KB Output is correct
9 Correct 728 ms 15344 KB Output is correct
10 Correct 1044 ms 15088 KB Output is correct
11 Correct 1062 ms 14936 KB Output is correct
12 Correct 1853 ms 15352 KB Output is correct
13 Correct 952 ms 14832 KB Output is correct
14 Correct 1292 ms 14292 KB Output is correct
15 Correct 1032 ms 14300 KB Output is correct
16 Correct 2673 ms 16240 KB Output is correct
17 Correct 2894 ms 17048 KB Output is correct
18 Correct 3225 ms 16968 KB Output is correct
19 Correct 1981 ms 16876 KB Output is correct
20 Correct 2907 ms 17204 KB Output is correct
21 Correct 3086 ms 17028 KB Output is correct
22 Correct 1952 ms 16364 KB Output is correct
23 Correct 4379 ms 23260 KB Output is correct
24 Correct 4645 ms 24360 KB Output is correct
25 Correct 3635 ms 24168 KB Output is correct
26 Correct 5648 ms 24168 KB Output is correct
27 Correct 6936 ms 24036 KB Output is correct
28 Correct 3361 ms 15864 KB Output is correct
29 Correct 3291 ms 15992 KB Output is correct
30 Correct 3282 ms 15904 KB Output is correct
31 Correct 3239 ms 15900 KB Output is correct
32 Correct 5720 ms 23652 KB Output is correct
33 Correct 5439 ms 22888 KB Output is correct
34 Correct 5385 ms 23784 KB Output is correct
35 Correct 5352 ms 24040 KB Output is correct
36 Correct 3838 ms 23528 KB Output is correct
37 Execution timed out 9085 ms 25620 KB Time limit exceeded
38 Halted 0 ms 0 KB -