oj.uz

Submission #225149

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

	swap(block[bi][pos[i].second], block[bi].back());
	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]);
	build(bi);

	return get();
}

void init(int N, int L, int X[])
{
	n = N;
	len = L;
	K = 300;	
	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++)
                  ~~^~~~~~~~~~~~~~~~~

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 10 ms 7424 KB Output is correct
6 Correct 9 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 10 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 1729 ms 8556 KB Output is correct
8 Correct 1812 ms 9792 KB Output is correct
9 Correct 2334 ms 11760 KB Output is correct
10 Correct 2233 ms 11376 KB Output is correct
11 Correct 2059 ms 11380 KB Output is correct
12 Correct 3537 ms 11640 KB Output is correct
13 Correct 2121 ms 11120 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 10 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 1729 ms 8556 KB Output is correct
8 Correct 1812 ms 9792 KB Output is correct
9 Correct 2334 ms 11760 KB Output is correct
10 Correct 2233 ms 11376 KB Output is correct
11 Correct 2059 ms 11380 KB Output is correct
12 Correct 3537 ms 11640 KB Output is correct
13 Correct 2121 ms 11120 KB Output is correct
14 Correct 2590 ms 10740 KB Output is correct
15 Correct 2914 ms 10740 KB Output is correct
16 Correct 5381 ms 12528 KB Output is correct
17 Correct 6281 ms 13608 KB Output is correct
18 Correct 6255 ms 13672 KB Output is correct
19 Correct 5774 ms 13292 KB Output is correct
20 Correct 6231 ms 13736 KB Output is correct
21 Correct 6076 ms 13480 KB Output is correct
22 Correct 3382 ms 12652 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 10 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 1729 ms 8556 KB Output is correct
8 Correct 1812 ms 9792 KB Output is correct
9 Correct 2334 ms 11760 KB Output is correct
10 Correct 2233 ms 11376 KB Output is correct
11 Correct 2059 ms 11380 KB Output is correct
12 Correct 3537 ms 11640 KB Output is correct
13 Correct 2121 ms 11120 KB Output is correct
14 Correct 2590 ms 10740 KB Output is correct
15 Correct 2914 ms 10740 KB Output is correct
16 Correct 5381 ms 12528 KB Output is correct
17 Correct 6281 ms 13608 KB Output is correct
18 Correct 6255 ms 13672 KB Output is correct
19 Correct 5774 ms 13292 KB Output is correct
20 Correct 6231 ms 13736 KB Output is correct
21 Correct 6076 ms 13480 KB Output is correct
22 Correct 3382 ms 12652 KB Output is correct
23 Execution timed out 9018 ms 20416 KB Time limit exceeded
24 Halted 0 ms 0 KB -