oj.uz

답안 #1089748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089748 2024-09-17T05:33:39 Z ymm 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 1561 ms 33248 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#define int ll

int L;

struct Part {
	vector<int> Ps;
	vector<pii> ans;

	void calc_ans() {
		ans.resize(Ps.size());
		if (ans.empty())
			return;
		ans.back() = {1, Ps.back() + L};
		size_t ptr = ans.size();
		LoopR (i,0,(ll)ans.size()-1) {
			while (Ps[ptr-1] - Ps[i] >= L)
				--ptr;
			ans[i].first = ptr == ans.size()? 1: ans[ptr].first + 1;
			ans[i].second = ptr == ans.size()? Ps[i] + L: ans[ptr].second;
		}
	}

	// vec must be sorted
	// O(vec.size())
	Part(const vector<int> &vec) {
		Ps = vec;
		calc_ans();
	}

	auto lower_bound(int x) {
		// implement caching mechanism if needed
		return std::lower_bound(Ps.begin(), Ps.end(), x);
	}

	// O(log(Ps.size()))
	pii get(int p) {
		auto it = lower_bound(p);
		if (it == Ps.end())
			return {0, p};
		return ans[it - Ps.begin()];
	}

	// O(Ps.size())
	void put(int x) {
		auto it = lower_bound(x);
		Ps.insert(it, x);
		calc_ans();
	}

	// O(Ps.size())
	void remove(int x) {
		auto it = lower_bound(x);
		assert(it != Ps.end() && *it == x);
		Ps.erase(it);
		calc_ans();
	}
};

struct PartList {
	vector<Part> parts;
	vector<int> bounds;
	map<int, int> pos_cnt;
	static constexpr int S = 1024;

	// O(nlog(n))
	void init(vector<int> vec) {
		pos_cnt.clear();
		sort(vec.begin(), vec.end());
		for (int x : vec)
			pos_cnt[x]++;
		repart(vec);
	}

	// Ps must be sorted
	// O(Ps.size())
	void repart(const vector<int> &Ps) {
		bounds.clear();
		parts.clear();
		for (size_t i = 0; i < Ps.size(); i += S) {
			size_t j = min<ll>(i + S, Ps.size());
			if (j != Ps.size())
				bounds.push_back(Ps[j]);
			parts.emplace_back(vector(Ps.begin() + i, Ps.begin() + j));
		}
	}

	// O(n)
	void repart() {
		vector<int> vec;
		for (auto &p : parts)
			vec.insert(vec.end(), p.Ps.begin(), p.Ps.end());
		repart(vec);
	}

	// O(log(n) + S) + amortized O(n/S)
	void move(int x, int y) {
		auto &cntx = pos_cnt[x];
		auto &cnty = pos_cnt[y];
		if (!--cntx) {
			int i = upper_bound(bounds.begin(), bounds.end(), x) - bounds.begin();
			parts[i].remove(x);
		}
		if (!cnty++) {
			int i = upper_bound(bounds.begin(), bounds.end(), y) - bounds.begin();
			parts[i].put(y);
			if (parts[i].Ps.size() > 2*S)
				repart();
		}
	}

	// O(n/S * log(S))
	int calc() {
		int ans = 0;
		int pnt = 0;
		for (auto &p : parts) {
			auto [x, y] = p.get(pnt);
			//cerr << "Ps = ";
			//for (auto x : p.Ps)
			//	cerr << x << ", ";
			//cerr << "\npnt = " << pnt << ", x = " << x << ", y = " << y << '\n';
			ans += x;
			pnt = y;
		}
		return ans;
	}
};

const int N = 350'010;
PartList part_list;
int pos[N];
int n;

void init(signed n_, signed L_, signed X[])
{
	n = n_;
	L = L_ + 1;
	Loop (i,0,n)
		pos[i] = X[i];
	part_list.init(vector(pos, pos + n));
}

signed update(signed i, signed y)
{
	part_list.move(pos[i], y);
	pos[i] = y;
	return part_list.calc();
}

// move = O(log(n) + S) + amortized O(n/S)
// calc = O(n/S * log(S))
// q log(n) + qS + nq/S + nq/S log(S)
// qS + nq/S log(S)
// S^2 / log(S) = n
// S = 1280

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 245 ms 5968 KB Output is correct
8 Correct 234 ms 6588 KB Output is correct
9 Correct 276 ms 8120 KB Output is correct
10 Correct 263 ms 10888 KB Output is correct
11 Correct 264 ms 10860 KB Output is correct
12 Correct 578 ms 10448 KB Output is correct
13 Correct 267 ms 10664 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 245 ms 5968 KB Output is correct
8 Correct 234 ms 6588 KB Output is correct
9 Correct 276 ms 8120 KB Output is correct
10 Correct 263 ms 10888 KB Output is correct
11 Correct 264 ms 10860 KB Output is correct
12 Correct 578 ms 10448 KB Output is correct
13 Correct 267 ms 10664 KB Output is correct
14 Correct 144 ms 6516 KB Output is correct
15 Correct 344 ms 9108 KB Output is correct
16 Correct 835 ms 11716 KB Output is correct
17 Correct 826 ms 14272 KB Output is correct
18 Correct 981 ms 14008 KB Output is correct
19 Correct 425 ms 15656 KB Output is correct
20 Correct 923 ms 14784 KB Output is correct
21 Correct 873 ms 14628 KB Output is correct
22 Correct 363 ms 14956 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 245 ms 5968 KB Output is correct
8 Correct 234 ms 6588 KB Output is correct
9 Correct 276 ms 8120 KB Output is correct
10 Correct 263 ms 10888 KB Output is correct
11 Correct 264 ms 10860 KB Output is correct
12 Correct 578 ms 10448 KB Output is correct
13 Correct 267 ms 10664 KB Output is correct
14 Correct 144 ms 6516 KB Output is correct
15 Correct 344 ms 9108 KB Output is correct
16 Correct 835 ms 11716 KB Output is correct
17 Correct 826 ms 14272 KB Output is correct
18 Correct 981 ms 14008 KB Output is correct
19 Correct 425 ms 15656 KB Output is correct
20 Correct 923 ms 14784 KB Output is correct
21 Correct 873 ms 14628 KB Output is correct
22 Correct 363 ms 14956 KB Output is correct
23 Correct 1561 ms 26580 KB Output is correct
24 Correct 1419 ms 25768 KB Output is correct
25 Correct 941 ms 24260 KB Output is correct
26 Correct 1079 ms 33248 KB Output is correct
27 Correct 1299 ms 33084 KB Output is correct
28 Incorrect 462 ms 8436 KB Output isn't correct
29 Halted 0 ms 0 KB -