oj.uz

답안 #225322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225322 2020-04-20T09:17:35 Z davitmarg 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 20268 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 = 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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 10 ms 10880 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 10 ms 10880 KB Output is correct
7 Correct 573 ms 12152 KB Output is correct
8 Correct 626 ms 12404 KB Output is correct
9 Correct 909 ms 13936 KB Output is correct
10 Correct 1246 ms 13808 KB Output is correct
11 Correct 1193 ms 13808 KB Output is correct
12 Correct 1959 ms 14192 KB Output is correct
13 Correct 1299 ms 13808 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 10 ms 10880 KB Output is correct
7 Correct 573 ms 12152 KB Output is correct
8 Correct 626 ms 12404 KB Output is correct
9 Correct 909 ms 13936 KB Output is correct
10 Correct 1246 ms 13808 KB Output is correct
11 Correct 1193 ms 13808 KB Output is correct
12 Correct 1959 ms 14192 KB Output is correct
13 Correct 1299 ms 13808 KB Output is correct
14 Correct 1102 ms 13068 KB Output is correct
15 Correct 1047 ms 13404 KB Output is correct
16 Correct 2954 ms 14700 KB Output is correct
17 Correct 3697 ms 15676 KB Output is correct
18 Correct 3902 ms 15596 KB Output is correct
19 Correct 2463 ms 15468 KB Output is correct
20 Correct 3609 ms 15760 KB Output is correct
21 Correct 3649 ms 15976 KB Output is correct
22 Correct 2183 ms 15340 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11008 KB Output is correct
2 Correct 10 ms 10880 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct
4 Correct 10 ms 10880 KB Output is correct
5 Correct 10 ms 11008 KB Output is correct
6 Correct 10 ms 10880 KB Output is correct
7 Correct 573 ms 12152 KB Output is correct
8 Correct 626 ms 12404 KB Output is correct
9 Correct 909 ms 13936 KB Output is correct
10 Correct 1246 ms 13808 KB Output is correct
11 Correct 1193 ms 13808 KB Output is correct
12 Correct 1959 ms 14192 KB Output is correct
13 Correct 1299 ms 13808 KB Output is correct
14 Correct 1102 ms 13068 KB Output is correct
15 Correct 1047 ms 13404 KB Output is correct
16 Correct 2954 ms 14700 KB Output is correct
17 Correct 3697 ms 15676 KB Output is correct
18 Correct 3902 ms 15596 KB Output is correct
19 Correct 2463 ms 15468 KB Output is correct
20 Correct 3609 ms 15760 KB Output is correct
21 Correct 3649 ms 15976 KB Output is correct
22 Correct 2183 ms 15340 KB Output is correct
23 Correct 7243 ms 19980 KB Output is correct
24 Correct 8090 ms 20268 KB Output is correct
25 Correct 6201 ms 20256 KB Output is correct
26 Execution timed out 9044 ms 20164 KB Time limit exceeded
27 Halted 0 ms 0 KB -