oj.uz

Submission #225150

# Submission time Handle Problem Language Result Execution time Memory
225150 2020-04-19T10:19:00 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;

	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 = 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++)
                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 9 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 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 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 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 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 1030 ms 8440 KB Output is correct
8 Correct 1203 ms 8948 KB Output is correct
9 Correct 2023 ms 9884 KB Output is correct
10 Correct 2027 ms 9944 KB Output is correct
11 Correct 1908 ms 9876 KB Output is correct
12 Correct 3566 ms 10048 KB Output is correct
13 Correct 1931 ms 9876 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 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 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 1030 ms 8440 KB Output is correct
8 Correct 1203 ms 8948 KB Output is correct
9 Correct 2023 ms 9884 KB Output is correct
10 Correct 2027 ms 9944 KB Output is correct
11 Correct 1908 ms 9876 KB Output is correct
12 Correct 3566 ms 10048 KB Output is correct
13 Correct 1931 ms 9876 KB Output is correct
14 Correct 2196 ms 9476 KB Output is correct
15 Correct 2287 ms 9332 KB Output is correct
16 Correct 5419 ms 10368 KB Output is correct
17 Correct 6560 ms 11460 KB Output is correct
18 Correct 6402 ms 11676 KB Output is correct
19 Correct 5364 ms 11244 KB Output is correct
20 Correct 6305 ms 11588 KB Output is correct
21 Correct 6047 ms 11636 KB Output is correct
22 Correct 3298 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 9 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 8 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 1030 ms 8440 KB Output is correct
8 Correct 1203 ms 8948 KB Output is correct
9 Correct 2023 ms 9884 KB Output is correct
10 Correct 2027 ms 9944 KB Output is correct
11 Correct 1908 ms 9876 KB Output is correct
12 Correct 3566 ms 10048 KB Output is correct
13 Correct 1931 ms 9876 KB Output is correct
14 Correct 2196 ms 9476 KB Output is correct
15 Correct 2287 ms 9332 KB Output is correct
16 Correct 5419 ms 10368 KB Output is correct
17 Correct 6560 ms 11460 KB Output is correct
18 Correct 6402 ms 11676 KB Output is correct
19 Correct 5364 ms 11244 KB Output is correct
20 Correct 6305 ms 11588 KB Output is correct
21 Correct 6047 ms 11636 KB Output is correct
22 Correct 3298 ms 11244 KB Output is correct
23 Execution timed out 9034 ms 14952 KB Time limit exceeded
24 Halted 0 ms 0 KB -