제출 #1089749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089749		ymm	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	97 / 100	1432 ms	25748 KiB

elephants

#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;

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 = 1<<22;
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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3