Submission #521623

#	Time	Username	Problem	Language	Result	Execution time	Memory
521623		amunduzbaev	IOI Fever (JOI21_fever)	C++14	100 / 100	2172 ms	54864 KiB

fever

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

// returns number of elements strictly smaller than v in vec
template<class T>
int bins(const vector<T>& vec, T v) {
	int low = 0;
	int high = vec.size();
	while(low != high) {
		int mid = (low + high) >> 1;
		if (vec[mid] < v) low = mid + 1;
		else high = mid;
	}
	return low;
}

// Struct for priority queue operations on index set [0, n-1]
// push(i, v) overwrites value at position i if one already exists
// decKey is faster but requires that the new key is smaller than the old one
struct Prique {
	const ll INF = (ll)1e18;
	vector<pair<ll, int>> data;
	const int n;

	Prique(int siz) : n(siz), data(2*siz, {INF, -1}) { data[0] = {-INF, -1}; }
	bool empty() const { return data[1].second >= INF; }
	pair<ll, int> top() const { return data[1]; }

	void push(int i, ll v) {
		data[i+n] = {v, (v >= INF ? -1 : i)};
		for (i += n; i > 1; i >>= 1) data[i>>1] = min(data[i], data[i^1]);
	}
	void decKey(int i, ll v) {
		for (int j = i+n; data[j].first > v; j >>= 1) data[j] = {v, i};
	}
	pair<ll, int> pop() {
		auto res = data[1];
		push(res.second, INF);
		return res;
	}
};

// Segment tree for range minimum and range capping
class SegTree {
	private:
		const ll INF = (ll)1e18;
		vector<ll> mn, cap, base;
		int h = 1;

		void apply(int i, ll v) {
			cap[i] = min(cap[i], v);
			mn[i] = min(mn[i], base[i] + cap[i]);
		}
		void push(int i) {
			apply(2*i, cap[i]);
			apply(2*i+1, cap[i]);
			cap[i] = INF;
		}

		void recApply(int a, int b, ll v, int i, int ia, int ib) {
			if (ib <= a || b <= ia) return;
			if (a <= ia && ib <= b) {
				apply(i, v);
			} else {
				push(i);
				int im = (ia + ib) >> 1;
				recApply(a, b, v, 2*i, ia, im);
				recApply(a, b, v, 2*i+1, im, ib);
				mn[i] = min(mn[2*i], mn[2*i+1]);
			}
		}
	public:
		SegTree(int n) {
			while(h < n) h *= 2;
			mn.resize(2*h, 2*INF); base.resize(2*h, INF); cap.resize(2*h, INF); 
		}
		void rangeCap(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); }
		ll getMinVal() { return mn[1]; }
		
		void setBase(int i, ll v) {
			i += h;
			base[i] = v;
			mn[i] = base[i] + cap[i];
			for (i >>= 1; i > 0; i >>= 1) {
				base[i] = min(base[2*i], base[2*i+1]);
				mn[i] = min(cap[i] + base[i], min(mn[2*i], mn[2*i+1]));
			}
		}

		pair<ll, int> getMin() {
			int i = 1;
			ll res = mn[1];
			while(i < h) {
				push(i);
				if (mn[2*i] == mn[i]) i = 2*i;
				else i = 2*i+1;
			}
			return {res, i - h};
		}
};

pair<int, int> rotate(pair<int, int> dir) {
	return {dir.second, -dir.first};
}
int sign(ll v) {
	return (v < 0 ? -1 : v > 0);
}

int solve(const vector<pair<ll, ll>>& pts) {
	int n = pts.size();
	vector<int> dir(n); // RIGHT DOWN LEFT UP
	dir[0] = 0;
	for (int i = 1; i < n; ++i) {
		ll dx = pts[i].first, dy = pts[i].second;
		if (abs(dx) > abs(dy)) {
			if (dx < 0) dir[i] = 0;
			else dir[i] = 2;
		} else if (abs(dy) > abs(dx) || dx > 0) {
			if (dy < 0) dir[i] = 3;
			else dir[i] = 1;
		} else {
			dir[i] = 0;
		}
	}

	vector<pair<int, int>> diffs(8);
	diffs[0] = {1, 0};
	diffs[1] = {1, -1};
	diffs[2] = {0, -1};
	diffs[3] = {-1, -1};
	diffs[4] = {-1, 0};
	diffs[5] = {-1, 1};
	diffs[6] = {0, 1};
	diffs[7] = {1, 1};
	
	vector<vector<array<ll, 4>>> ords(8);
	for (int i = 0; i < n; ++i) {
		int dx = sign(diffs[2*dir[i]].first);
		int dy = sign(diffs[2*dir[i]].second);
		for (int j = 0; j < 8; ++j) {
			if (sign(diffs[j].first) != -dx && sign(diffs[j].second) != -dy) continue;
			array<ll, 4> off;
			off[0] = dir[i];
			
			pair<int, int> tar = diffs[j];
			pair<int, int> ortho = rotate(tar);
			off[1] = ortho.first * pts[i].first + ortho.second * pts[i].second;
			off[2] = tar.first * pts[i].first + tar.second * pts[i].second;
			off[3] = i;

			ords[j].push_back(off);
		}
	}
	for (int j = 0; j < 8; ++j) sort(ords[j].begin(), ords[j].end());
	
	vector<SegTree> segs;
	for (int j = 0; j < 8; ++j) {
		segs.emplace_back(ords[j].size());
		for (int i = 0; i < ords[j].size(); ++i) {
			if (ords[j][i][3] == 0) {
				segs[j].setBase(i, 0);
				segs[j].rangeCap(i, i, 0);
			} else {
				segs[j].setBase(i, ords[j][i][2]);
			}
		}
	}

	Prique pq(8);
	for (int j = 0; j < 8; ++j) pq.decKey(j, segs[j].getMin().first);

	vector<ll> times(n, INF);
	
	for (int j = pq.pop().second; j != -1; j = pq.pop().second) {
		auto opt = segs[j].getMin();
		segs[j].setBase(opt.second, INF);
		pq.decKey(j, segs[j].getMinVal());

		int i = ords[j][opt.second][3];
		ll t = opt.first;

		if (t >= INF / 2) break;
		if (t >= times[i]) continue;
		times[i] = t;
		
		int d = dir[i];
		for (int j2 = 0; j2 < 8; ++j2) {
			array<ll, 4> ind;

			// Desired direction
			if (j2 == (2*d+7) % 8) ind[0] = (d+1) % 4;
			else if (j2 == 2*d) ind[0] = (d + 2) % 4;
			else if (j2 == (2*d+1) % 8) ind[0] = (d+3) % 4;
			else continue;

			// Desired line
			pair<int, int> ortho = rotate(diffs[j2]);
			ind[1] = ortho.first * pts[i].first + ortho.second * pts[i].second;

			// Desired min coordinate
			ll base = diffs[j2].first * pts[i].first + diffs[j2].second * pts[i].second;
			ind[2] = t + base;

			// OK indices
			ind[3] = -1;
			
			int i0 = bins(ords[j2], ind);

			ind[2] = INF;
			
			int i1 = bins(ords[j2], ind);

			segs[j2].rangeCap(i0, i1 - 1, -base);
			pq.decKey(j2, segs[j2].getMinVal());
		}
	}

	int res = 0;
	for (ll& v : times) res += (v < INF);
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	vector<pair<ll, ll>> pts(n);
	for (int i = 0; i < n; ++i) {
		int y, x;
		cin >> y >> x;
		pts[i] = {y, x};
	}
	for (int i = 1; i < n; ++i) {
		pts[i].first -= pts[0].first;
		pts[i].second -= pts[0].second;
	}
	pts[0] = {0, 0};

	// Decide direction person 1 goes to
	int res = 0;
	res = max(res, solve(pts)); // Right
	for (auto& pr : pts) pr.first = -pr.first;
	res = max(res, solve(pts)); // Left
	for (auto& pr : pts) swap(pr.first, pr.second);
	res = max(res, solve(pts)); // Up
	for (auto& pr : pts) pr.first = -pr.first;
	res = max(res, solve(pts)); // Down

	cout << res << '\n';
}

Compilation message (stderr)

fever.cpp: In constructor 'Prique::Prique(int)':
fever.cpp:25:12: warning: 'Prique::n' will be initialized after [-Wreorder]
   25 |  const int n;
      |            ^
fever.cpp:24:24: warning:   'std::vector<std::pair<long long int, int> > Prique::data' [-Wreorder]
   24 |  vector<pair<ll, int>> data;
      |                        ^~~~
fever.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  Prique(int siz) : n(siz), data(2*siz, {INF, -1}) { data[0] = {-INF, -1}; }
      |  ^~~~~~
fever.cpp: In function 'int solve(const std::vector<std::pair<long long int, long long int> >&)':
fever.cpp:161:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |   for (int i = 0; i < ords[j].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31