oj.uz

Submission #225154

# Submission time Handle Problem Language Result Execution time Memory
225154 2020-04-19T10:23:26 Z davitmarg Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 14952 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;
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());
	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 = upper_bound(all(block[i]), MP(block[i][j].first + len, n)) - block[i].begin();
		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 = sqrt(n) + 1;
	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:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < block[i].size(); j++)
                  ~~^~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:109: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 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 816 ms 8508 KB Output is correct
8 Correct 969 ms 9052 KB Output is correct
9 Correct 1578 ms 9988 KB Output is correct
10 Correct 1785 ms 9968 KB Output is correct
11 Correct 1662 ms 9964 KB Output is correct
12 Correct 3035 ms 10224 KB Output is correct
13 Correct 1660 ms 9880 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 816 ms 8508 KB Output is correct
8 Correct 969 ms 9052 KB Output is correct
9 Correct 1578 ms 9988 KB Output is correct
10 Correct 1785 ms 9968 KB Output is correct
11 Correct 1662 ms 9964 KB Output is correct
12 Correct 3035 ms 10224 KB Output is correct
13 Correct 1660 ms 9880 KB Output is correct
14 Correct 1791 ms 9200 KB Output is correct
15 Correct 1757 ms 9332 KB Output is correct
16 Correct 4543 ms 10608 KB Output is correct
17 Correct 5370 ms 11628 KB Output is correct
18 Correct 5382 ms 11372 KB Output is correct
19 Correct 3790 ms 11248 KB Output is correct
20 Correct 5445 ms 11500 KB Output is correct
21 Correct 5370 ms 11472 KB Output is correct
22 Correct 2892 ms 11244 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 816 ms 8508 KB Output is correct
8 Correct 969 ms 9052 KB Output is correct
9 Correct 1578 ms 9988 KB Output is correct
10 Correct 1785 ms 9968 KB Output is correct
11 Correct 1662 ms 9964 KB Output is correct
12 Correct 3035 ms 10224 KB Output is correct
13 Correct 1660 ms 9880 KB Output is correct
14 Correct 1791 ms 9200 KB Output is correct
15 Correct 1757 ms 9332 KB Output is correct
16 Correct 4543 ms 10608 KB Output is correct
17 Correct 5370 ms 11628 KB Output is correct
18 Correct 5382 ms 11372 KB Output is correct
19 Correct 3790 ms 11248 KB Output is correct
20 Correct 5445 ms 11500 KB Output is correct
21 Correct 5370 ms 11472 KB Output is correct
22 Correct 2892 ms 11244 KB Output is correct
23 Execution timed out 9017 ms 14952 KB Time limit exceeded
24 Halted 0 ms 0 KB -