Submission #211706

#	Time	Username	Problem	Language	Result	Execution time	Memory
211706		DrumpfTheGodEmperor	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	775 ms	97424 KiB

timeleap

#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 3e5 + 5;
int le[N], ri[N];
struct Node {
	int st, en, len, cost;
	//We start at [st....st + len], and ends at [en...en + len]
	Node(int st = -1, int en = -1, int len = 0, int cost = 0): st(st), en(en), len(len), cost(cost) {};
	int get(int x, int y) {
		int ans = cost;
		if (x < st) x = st;
		if (x > st + len) {
//				cout << "x = " << x << " st + len = " << st + len << "\n";
			ans += (x - st - len);
			x = st + len;
		}
		x += (en - st);
		if (y < x) ans += (x - y);
		return ans;
	}
};
Node operator+(Node lhs, Node rhs) {
	if (lhs.st == -1) return rhs;
	if (rhs.st == -1) return lhs;
	//2 sections does not intersect
	if (lhs.en + lhs.len < rhs.st) {
		return Node(lhs.st + lhs.len, rhs.en, 0, lhs.cost + rhs.cost);
	} else if (rhs.st + rhs.len < lhs.en) {
		return Node(lhs.st, rhs.en + rhs.len, 0, lhs.cost + rhs.cost + (lhs.en - rhs.st - rhs.len));
	} else {
		//2 sections [lhs.en...lhs.en + lhs.len] and [rhs.st....rhs.st + rhs.len] do intersect.
		int l = max(lhs.en, rhs.st), r = min(lhs.en + lhs.len, rhs.st + rhs.len);
		int diffl = lhs.en - lhs.st, diffr = rhs.en - rhs.st;
		
		return Node(l - diffl, l + diffr, r - l, lhs.cost + rhs.cost);
	}
}
class SegTree {
private:
	Node t[N << 2];
	void build(int l, int r, int x) {
		assert(l <= r);
		if (l == r) {
			if (!rev) t[x] = Node(le[l], le[l] + 1, ri[l] - le[l], 0);
			else t[x] = Node(le[n - 1 - l], le[n - 1 - l] + 1, ri[n - 1 - l] - le[n - 1 - l], 0);
//			cout << "t[" << l << "->" << r << "].st = " << t[x].st << " en = " << t[x].en << " len = " << t[x].len << "\n";
			return;
		}
		int m = (l + r) >> 1;
		build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
		t[x] = t[x << 1] + t[x << 1 | 1];
//		cout << "t[" << l << "->" << r << "].st = " << t[x].st << " en = " << t[x].en << " len = " << t[x].len << "\n";
	}
	void upd(int l, int r, int pos, int x) {
		assert(l <= r);
		if (l == r) {
			if (!rev) t[x] = Node(le[l], le[l] + 1, ri[l] - le[l], 0);
			else t[x] = Node(le[n - 1 - l], le[n - 1 - l] + 1, ri[n - 1 - l] - le[n - 1 - l], 0);
			return;
		}
		int m = (l + r) >> 1;
		if (pos <= m) upd(l, m, pos, x << 1);
		else upd(m + 1, r, pos, x << 1 | 1);
		t[x] = t[x << 1] + t[x << 1 | 1];
//		cout << "t[" << x << "].st = " << t[x].st << "\n";
	}
	Node get(int l, int r, int s, int e, int x) {
		assert(l <= r);
		if (l > e || r < s) return Node();
		if (s <= l && r <= e) return t[x];
		int m = (l + r) >> 1;
		return get(l, m, s, e, x << 1) + get(m + 1, r, s, e, x << 1 | 1);
	}
public:
	int n;
	bool rev;
	void init(int _n, bool _rev) {
		n = _n;
		rev = _rev;
		build(0, n - 1, 1);
	}
	void upd(int pos) {
		assert(pos >= 0 && pos < n);
		if (!rev) upd(0, n - 1, pos, 1);
		else upd(0, n - 1, n - 1 - pos, 1);
	}
	int get(int a, int b, int x, int y) {
//		cout << "a = " << a << " b = " << b << "\n";
		assert(a >= 0 && b >= 0 && a < n && b - 1 < n);
		Node ans = get(0, n - 1, a, b - 1, 1);
//		cout << ans.st << " " << ans.en << " " << ans.len << " cost = " << ans.cost << "\n";
		return ans.get(x, y);
	}
} st, st2;
int n, q;
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	fw (i, 0, n - 1) {
		cin >> le[i] >> ri[i];
		ri[i]--;
	}
//	We want to go from city A to B, there is some segment of time that allows us to spend the minimum cost.
//	Everything outside the range can be moved into the range and spend the aforementioned cost.
	if (n > 1) {
		st.init(n - 1, 0);
		st2.init(n - 1, 1);
	}
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int p, s, e;
			cin >> p >> s >> e;
			p--;
			le[p] = s, ri[p] = e - 1;
			st.upd(p);
			st2.upd(p);
		} else {
			int a, b, x, y;
			cin >> a >> x >> b >> y;
			if (a == b) {
				if (y < x) cout << x - y << "\n";
				else cout << "0\n";
				continue;
			}
			if (a < b) {
				a--, b--;
				cout << st.get(a, b, x, y) << "\n";
			} else {
				a--, b--;
				a = n - 1 - a, b = n - 1 - b;
				cout << st2.get(a, b, x, y) << "\n";
			}
		}
	}
	return 0;
}

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