oj.uz

Submission #225163

# Submission time Handle Problem Language Result Execution time Memory
225163 2020-04-19T10:33:31 Z davitmarg Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 25772 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;
		}
	}

	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 = 500;
	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 12 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 10 ms 10880 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 10 ms 10880 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 11 ms 10880 KB Output is correct
6 Correct 10 ms 10880 KB Output is correct
7 Correct 791 ms 12128 KB Output is correct
8 Correct 837 ms 12276 KB Output is correct
9 Correct 915 ms 13552 KB Output is correct
10 Correct 1116 ms 13552 KB Output is correct
11 Correct 1085 ms 13552 KB Output is correct
12 Correct 1667 ms 13936 KB Output is correct
13 Correct 1119 ms 13552 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 10 ms 10880 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 11 ms 10880 KB Output is correct
6 Correct 10 ms 10880 KB Output is correct
7 Correct 791 ms 12128 KB Output is correct
8 Correct 837 ms 12276 KB Output is correct
9 Correct 915 ms 13552 KB Output is correct
10 Correct 1116 ms 13552 KB Output is correct
11 Correct 1085 ms 13552 KB Output is correct
12 Correct 1667 ms 13936 KB Output is correct
13 Correct 1119 ms 13552 KB Output is correct
14 Correct 1157 ms 12876 KB Output is correct
15 Correct 1245 ms 12828 KB Output is correct
16 Correct 2538 ms 13936 KB Output is correct
17 Correct 2911 ms 14976 KB Output is correct
18 Correct 3026 ms 15096 KB Output is correct
19 Correct 1926 ms 14444 KB Output is correct
20 Correct 2874 ms 15048 KB Output is correct
21 Correct 2858 ms 15080 KB Output is correct
22 Correct 1928 ms 14572 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 10 ms 10880 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 11 ms 10880 KB Output is correct
6 Correct 10 ms 10880 KB Output is correct
7 Correct 791 ms 12128 KB Output is correct
8 Correct 837 ms 12276 KB Output is correct
9 Correct 915 ms 13552 KB Output is correct
10 Correct 1116 ms 13552 KB Output is correct
11 Correct 1085 ms 13552 KB Output is correct
12 Correct 1667 ms 13936 KB Output is correct
13 Correct 1119 ms 13552 KB Output is correct
14 Correct 1157 ms 12876 KB Output is correct
15 Correct 1245 ms 12828 KB Output is correct
16 Correct 2538 ms 13936 KB Output is correct
17 Correct 2911 ms 14976 KB Output is correct
18 Correct 3026 ms 15096 KB Output is correct
19 Correct 1926 ms 14444 KB Output is correct
20 Correct 2874 ms 15048 KB Output is correct
21 Correct 2858 ms 15080 KB Output is correct
22 Correct 1928 ms 14572 KB Output is correct
23 Correct 5475 ms 18788 KB Output is correct
24 Correct 6129 ms 23784 KB Output is correct
25 Correct 4777 ms 23780 KB Output is correct
26 Correct 7517 ms 23656 KB Output is correct
27 Correct 7619 ms 23528 KB Output is correct
28 Correct 2639 ms 16008 KB Output is correct
29 Correct 2610 ms 15992 KB Output is correct
30 Correct 2628 ms 15992 KB Output is correct
31 Correct 2587 ms 16016 KB Output is correct
32 Correct 6654 ms 23016 KB Output is correct
33 Correct 6831 ms 22376 KB Output is correct
34 Correct 6916 ms 23272 KB Output is correct
35 Correct 7017 ms 23528 KB Output is correct
36 Correct 4726 ms 23144 KB Output is correct
37 Execution timed out 9052 ms 25772 KB Time limit exceeded
38 Halted 0 ms 0 KB -