oj.uz

Submission #225158

# Submission time Handle Problem Language Result Execution time Memory
225158 2020-04-19T10:25:31 Z davitmarg Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 14568 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 = 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: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 9 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 9 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 1977 ms 8448 KB Output is correct
8 Correct 2045 ms 8564 KB Output is correct
9 Correct 2280 ms 9840 KB Output is correct
10 Correct 2718 ms 9840 KB Output is correct
11 Correct 2332 ms 9840 KB Output is correct
12 Correct 3268 ms 10352 KB Output is correct
13 Correct 2528 ms 9848 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 9 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 1977 ms 8448 KB Output is correct
8 Correct 2045 ms 8564 KB Output is correct
9 Correct 2280 ms 9840 KB Output is correct
10 Correct 2718 ms 9840 KB Output is correct
11 Correct 2332 ms 9840 KB Output is correct
12 Correct 3268 ms 10352 KB Output is correct
13 Correct 2528 ms 9848 KB Output is correct
14 Correct 2500 ms 9320 KB Output is correct
15 Correct 3035 ms 9460 KB Output is correct
16 Correct 4887 ms 10468 KB Output is correct
17 Correct 5459 ms 11092 KB Output is correct
18 Correct 5365 ms 11408 KB Output is correct
19 Correct 4341 ms 10604 KB Output is correct
20 Correct 5463 ms 11372 KB Output is correct
21 Correct 5182 ms 11436 KB Output is correct
22 Correct 4006 ms 10732 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 9 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 1977 ms 8448 KB Output is correct
8 Correct 2045 ms 8564 KB Output is correct
9 Correct 2280 ms 9840 KB Output is correct
10 Correct 2718 ms 9840 KB Output is correct
11 Correct 2332 ms 9840 KB Output is correct
12 Correct 3268 ms 10352 KB Output is correct
13 Correct 2528 ms 9848 KB Output is correct
14 Correct 2500 ms 9320 KB Output is correct
15 Correct 3035 ms 9460 KB Output is correct
16 Correct 4887 ms 10468 KB Output is correct
17 Correct 5459 ms 11092 KB Output is correct
18 Correct 5365 ms 11408 KB Output is correct
19 Correct 4341 ms 10604 KB Output is correct
20 Correct 5463 ms 11372 KB Output is correct
21 Correct 5182 ms 11436 KB Output is correct
22 Correct 4006 ms 10732 KB Output is correct
23 Execution timed out 9019 ms 14568 KB Time limit exceeded
24 Halted 0 ms 0 KB -