Submission #206688

#	Time	Username	Problem	Language	Result	Execution time	Memory
206688		atoiz	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	554 ms	49016 KiB

timeleap

#include <iostream>
#include <cassert>

using namespace std;

const int MAXN = 300007, INF = 1e9 + 7;

struct Path
{
	int from, to, len;
	int64_t cost;

	Path(int _from = 0, int _to = 0, int _len = INF, int64_t _cost = 0):
		from(_from), to(_to), len(_len), cost(_cost) {}

	void from_edge(int l, int r)
	{
		cost = 1;
		from = l, to = l + 1, len = r - l;
	}

	friend Path operator+ (Path lhs, Path rhs)
	{
		if (lhs.to + lhs.len < rhs.from) {
			return {lhs.from + lhs.len, rhs.to, 0, lhs.cost + (rhs.from - (lhs.to + lhs.len)) + rhs.cost};
		} else if (rhs.from + rhs.len < lhs.to) {
			return {lhs.from, rhs.to + rhs.len, 0, lhs.cost + (lhs.to - (rhs.from + rhs.len)) + rhs.cost};
		} else {
			if (lhs.to < rhs.from) {
				int d = rhs.from - lhs.to;
				lhs.from += d, lhs.to += d, lhs.len -= d;
			} else {
				int d = lhs.to - rhs.from;
				rhs.from += d, rhs.to += d, rhs.len -= d;
			}

			if (lhs.to + lhs.len < rhs.from + rhs.len) {
				rhs.len -= (rhs.from + rhs.len) - (lhs.to + lhs.len);
			} else {
				lhs.len -= (lhs.to + lhs.len) - (rhs.from + rhs.len);
			}

			assert(lhs.len == rhs.len);
			return {lhs.from, rhs.to, lhs.len, lhs.cost + rhs.cost};
		}
	}

	int64_t get(int x, int y)
	{
		int64_t ans = cost;

		int pos = x;
		if (pos < from) ans += from - pos, pos = from;
		if (pos > from + len) ans += pos - (from + len), pos = from + len;

		pos += to - from;
		ans += abs(pos - y);

		ans = (ans - (y - x)) / 2;
		return ans;
	}
} fw[MAXN << 1], bw[MAXN << 1];

int N, Q;

void modify(int i, int l, int r)
{
	for (i += N, fw[i].from_edge(l, r), bw[i].from_edge(l, r), i >>= 1; i >= 1; i >>= 1) {
		fw[i] = fw[i << 1] + fw[i << 1 | 1];
		bw[i] = bw[i << 1 | 1] + bw[i << 1];
	}
}

Path get_fw(int l, int r)
{
	Path lef, rig;
	for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
		if (l & 1) lef = lef + fw[l++];
		if (r & 1) rig = fw[--r] + rig;
	}
	return lef + rig;
}

Path get_bw(int l, int r)
{
	Path lef, rig;
	for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
		if (l & 1) rig = bw[l++] + rig;
		if (r & 1) lef = lef + bw[--r];
	}
	return lef + rig;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> Q;
	for (int i = 1; i < N; ++i) {
		int l, r;
		cin >> l >> r;
		modify(i, l, r - 1);
	}

	for (int i = N - 1; i >= 1; --i) {
		fw[i] = fw[i << 1] + fw[i << 1 | 1];
		bw[i] = bw[i << 1 | 1] + bw[i << 1];
	}

	while (Q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int i, l, r;
			cin >> i >> l >> r;
			modify(i, l, r - 1);
		} else {
			int l, r, x, y;
			cin >> l >> x >> r >> y;
			if (l <= r) cout << get_fw(l, r).get(x, y) << '\n';
			else cout << get_bw(r, l).get(x, y) << '\n';
		}
	}

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66