oj.uz

답안 #1089743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089743 2024-09-17T05:22:00 Z ymm 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
0 / 100
 1 ms 452 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;

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 = 1280;

	// 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(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 = 150'010;
PartList part_list;
int pos[N];
int n;

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

int update(int i, int 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -