oj.uz

Submission #225164

# Submission time Handle Problem Language Result Execution time Memory
225164 2020-04-19T10:36:20 Z davitmarg Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 21352 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 = 400;
	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 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 10 ms 10880 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 10 ms 10880 KB Output is correct
6 Correct 10 ms 11008 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 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 10 ms 10880 KB Output is correct
6 Correct 10 ms 11008 KB Output is correct
7 Correct 678 ms 12024 KB Output is correct
8 Correct 713 ms 12276 KB Output is correct
9 Correct 884 ms 13552 KB Output is correct
10 Correct 1141 ms 13552 KB Output is correct
11 Correct 1118 ms 13552 KB Output is correct
12 Correct 1724 ms 13808 KB Output is correct
13 Correct 1160 ms 13552 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 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 10 ms 10880 KB Output is correct
6 Correct 10 ms 11008 KB Output is correct
7 Correct 678 ms 12024 KB Output is correct
8 Correct 713 ms 12276 KB Output is correct
9 Correct 884 ms 13552 KB Output is correct
10 Correct 1141 ms 13552 KB Output is correct
11 Correct 1118 ms 13552 KB Output is correct
12 Correct 1724 ms 13808 KB Output is correct
13 Correct 1160 ms 13552 KB Output is correct
14 Correct 1054 ms 12816 KB Output is correct
15 Correct 1114 ms 12784 KB Output is correct
16 Correct 2615 ms 14056 KB Output is correct
17 Correct 3076 ms 14828 KB Output is correct
18 Correct 3244 ms 15084 KB Output is correct
19 Correct 2025 ms 14700 KB Output is correct
20 Correct 3061 ms 14956 KB Output is correct
21 Correct 3068 ms 15104 KB Output is correct
22 Correct 2039 ms 14700 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 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 10 ms 10880 KB Output is correct
6 Correct 10 ms 11008 KB Output is correct
7 Correct 678 ms 12024 KB Output is correct
8 Correct 713 ms 12276 KB Output is correct
9 Correct 884 ms 13552 KB Output is correct
10 Correct 1141 ms 13552 KB Output is correct
11 Correct 1118 ms 13552 KB Output is correct
12 Correct 1724 ms 13808 KB Output is correct
13 Correct 1160 ms 13552 KB Output is correct
14 Correct 1054 ms 12816 KB Output is correct
15 Correct 1114 ms 12784 KB Output is correct
16 Correct 2615 ms 14056 KB Output is correct
17 Correct 3076 ms 14828 KB Output is correct
18 Correct 3244 ms 15084 KB Output is correct
19 Correct 2025 ms 14700 KB Output is correct
20 Correct 3061 ms 14956 KB Output is correct
21 Correct 3068 ms 15104 KB Output is correct
22 Correct 2039 ms 14700 KB Output is correct
23 Correct 6067 ms 18920 KB Output is correct
24 Correct 6703 ms 18952 KB Output is correct
25 Correct 5267 ms 18972 KB Output is correct
26 Correct 8569 ms 18920 KB Output is correct
27 Correct 8591 ms 18920 KB Output is correct
28 Correct 2267 ms 13048 KB Output is correct
29 Correct 2199 ms 13052 KB Output is correct
30 Correct 2258 ms 12944 KB Output is correct
31 Correct 2226 ms 13176 KB Output is correct
32 Correct 7728 ms 18920 KB Output is correct
33 Correct 7976 ms 18920 KB Output is correct
34 Correct 7990 ms 18920 KB Output is correct
35 Correct 8234 ms 18920 KB Output is correct
36 Correct 5258 ms 18924 KB Output is correct
37 Execution timed out 9040 ms 21352 KB Time limit exceeded
38 Halted 0 ms 0 KB -