oj.uz

Submission #211706

# Submission time Handle Problem Language Result Execution time Memory
211706 2020-03-21T03:45:17 Z DrumpfTheGodEmperor Bitaro, who Leaps through Time (JOI19_timeleap) C++14
100 / 100
 775 ms 97424 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 75516 KB Output is correct
2 Correct 39 ms 75512 KB Output is correct
3 Correct 40 ms 75512 KB Output is correct
4 Correct 45 ms 75768 KB Output is correct
5 Correct 39 ms 75512 KB Output is correct
6 Correct 40 ms 75512 KB Output is correct
7 Correct 39 ms 75484 KB Output is correct
8 Correct 39 ms 75512 KB Output is correct
9 Correct 40 ms 75512 KB Output is correct
10 Correct 39 ms 75520 KB Output is correct
11 Correct 50 ms 75640 KB Output is correct
12 Correct 45 ms 75512 KB Output is correct
13 Correct 52 ms 75512 KB Output is correct
14 Correct 41 ms 75512 KB Output is correct
15 Correct 39 ms 75512 KB Output is correct
16 Correct 40 ms 75512 KB Output is correct
17 Correct 46 ms 75512 KB Output is correct
18 Correct 41 ms 75496 KB Output is correct
19 Correct 41 ms 75520 KB Output is correct
20 Correct 40 ms 75512 KB Output is correct
21 Correct 47 ms 75512 KB Output is correct
22 Correct 41 ms 75520 KB Output is correct
23 Correct 41 ms 75512 KB Output is correct
24 Correct 42 ms 75512 KB Output is correct
25 Correct 40 ms 75512 KB Output is correct
26 Correct 40 ms 75512 KB Output is correct
27 Correct 40 ms 75512 KB Output is correct
28 Correct 41 ms 75512 KB Output is correct
29 Correct 39 ms 75520 KB Output is correct
30 Correct 44 ms 75520 KB Output is correct
31 Correct 40 ms 75520 KB Output is correct
32 Correct 40 ms 75512 KB Output is correct
33 Correct 41 ms 75512 KB Output is correct
34 Correct 41 ms 75512 KB Output is correct
35 Correct 40 ms 75512 KB Output is correct
36 Correct 40 ms 75512 KB Output is correct
37 Correct 44 ms 75520 KB Output is correct
38 Correct 41 ms 75520 KB Output is correct
39 Correct 40 ms 75512 KB Output is correct
40 Correct 40 ms 75512 KB Output is correct
41 Correct 39 ms 75520 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 84064 KB Output is correct
2 Correct 661 ms 83892 KB Output is correct
3 Correct 666 ms 84092 KB Output is correct
4 Correct 655 ms 83704 KB Output is correct
5 Correct 675 ms 84108 KB Output is correct
6 Correct 680 ms 84088 KB Output is correct
7 Correct 671 ms 84216 KB Output is correct
8 Correct 775 ms 84436 KB Output is correct
9 Correct 672 ms 83832 KB Output is correct
10 Correct 773 ms 84216 KB Output is correct
11 Correct 662 ms 84088 KB Output is correct
12 Correct 698 ms 84472 KB Output is correct
13 Correct 652 ms 84472 KB Output is correct
14 Correct 40 ms 75508 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 75516 KB Output is correct
2 Correct 39 ms 75512 KB Output is correct
3 Correct 40 ms 75512 KB Output is correct
4 Correct 45 ms 75768 KB Output is correct
5 Correct 39 ms 75512 KB Output is correct
6 Correct 40 ms 75512 KB Output is correct
7 Correct 39 ms 75484 KB Output is correct
8 Correct 39 ms 75512 KB Output is correct
9 Correct 40 ms 75512 KB Output is correct
10 Correct 39 ms 75520 KB Output is correct
11 Correct 50 ms 75640 KB Output is correct
12 Correct 45 ms 75512 KB Output is correct
13 Correct 52 ms 75512 KB Output is correct
14 Correct 41 ms 75512 KB Output is correct
15 Correct 39 ms 75512 KB Output is correct
16 Correct 40 ms 75512 KB Output is correct
17 Correct 46 ms 75512 KB Output is correct
18 Correct 41 ms 75496 KB Output is correct
19 Correct 41 ms 75520 KB Output is correct
20 Correct 40 ms 75512 KB Output is correct
21 Correct 47 ms 75512 KB Output is correct
22 Correct 41 ms 75520 KB Output is correct
23 Correct 41 ms 75512 KB Output is correct
24 Correct 42 ms 75512 KB Output is correct
25 Correct 40 ms 75512 KB Output is correct
26 Correct 40 ms 75512 KB Output is correct
27 Correct 40 ms 75512 KB Output is correct
28 Correct 41 ms 75512 KB Output is correct
29 Correct 39 ms 75520 KB Output is correct
30 Correct 44 ms 75520 KB Output is correct
31 Correct 40 ms 75520 KB Output is correct
32 Correct 40 ms 75512 KB Output is correct
33 Correct 41 ms 75512 KB Output is correct
34 Correct 41 ms 75512 KB Output is correct
35 Correct 40 ms 75512 KB Output is correct
36 Correct 40 ms 75512 KB Output is correct
37 Correct 44 ms 75520 KB Output is correct
38 Correct 41 ms 75520 KB Output is correct
39 Correct 40 ms 75512 KB Output is correct
40 Correct 40 ms 75512 KB Output is correct
41 Correct 39 ms 75520 KB Output is correct
42 Correct 661 ms 84064 KB Output is correct
43 Correct 661 ms 83892 KB Output is correct
44 Correct 666 ms 84092 KB Output is correct
45 Correct 655 ms 83704 KB Output is correct
46 Correct 675 ms 84108 KB Output is correct
47 Correct 680 ms 84088 KB Output is correct
48 Correct 671 ms 84216 KB Output is correct
49 Correct 775 ms 84436 KB Output is correct
50 Correct 672 ms 83832 KB Output is correct
51 Correct 773 ms 84216 KB Output is correct
52 Correct 662 ms 84088 KB Output is correct
53 Correct 698 ms 84472 KB Output is correct
54 Correct 652 ms 84472 KB Output is correct
55 Correct 40 ms 75508 KB Output is correct
56 Correct 714 ms 96448 KB Output is correct
57 Correct 708 ms 95884 KB Output is correct
58 Correct 687 ms 96632 KB Output is correct
59 Correct 708 ms 96868 KB Output is correct
60 Correct 685 ms 96076 KB Output is correct
61 Correct 739 ms 97400 KB Output is correct
62 Correct 732 ms 96992 KB Output is correct
63 Correct 692 ms 97016 KB Output is correct
64 Correct 717 ms 97160 KB Output is correct
65 Correct 717 ms 96596 KB Output is correct
66 Correct 718 ms 96760 KB Output is correct
67 Correct 718 ms 97144 KB Output is correct
68 Correct 688 ms 95968 KB Output is correct
69 Correct 727 ms 97424 KB Output is correct
70 Correct 689 ms 95992 KB Output is correct
71 Correct 688 ms 95076 KB Output is correct
72 Correct 713 ms 95588 KB Output is correct
73 Correct 723 ms 96632 KB Output is correct
74 Correct 708 ms 96888 KB Output is correct
75 Correct 716 ms 96760 KB Output is correct
76 Correct 727 ms 97376 KB Output is correct
77 Correct 39 ms 75520 KB Output is correct