Submission #1171824

#TimeUsernameProblemLanguageResultExecution timeMemory
1171824M_W_13Bitaro, who Leaps through Time (JOI19_timeleap)C++20
100 / 100
551 ms51764 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) typedef long long ll; #define pb push_back #define st first #define nd second const int MAXN = 1 << 19; struct pt { ll l, r; ll czas; ll travel; }; pt polacz(pt a, pt b) { pt w; b.l -= a.czas; b.r -= a.czas; if (b.r < a.l) { w.travel = a.l - b.r; w.czas = a.czas + b.czas - w.travel; w.travel += a.travel + b.travel; w.l = a.l; w.r = a.l; return w; } w.l = min(a.r, max(a.l, b.l)); w.r = max(a.l, min(a.r, b.r)); w.czas = a.czas + b.czas + max(0ll, b.l - w.r); w.travel = a.travel + b.travel; return w; } pt seg[2 * MAXN]; pt seg2[2 * MAXN]; void upd(int v, pt x) { v += MAXN; seg[v] = x; v /= 2; while (v > 0) { seg[v] = polacz(seg[2 * v], seg[2 * v + 1]); v /= 2; } } void upd2(int v, pt x) { v += MAXN; seg2[v] = x; v /= 2; while (v > 0) { seg2[v] = polacz(seg2[2 * v + 1], seg2[2 * v]); v /= 2; } } pt query(int l, int r) { vector<pt> vec1; vector<pt> vec2; l += MAXN; r += MAXN; while (l < r) { if (l % 2 == 1) { vec1.pb(seg[l]); l++; } if (r % 2 == 0) { vec2.pb(seg[r]); r--; } l /= 2; r /= 2; } if (l == r) { vec1.pb(seg[l]); } vector<pt> vec; int sz1 = vec1.size(); int sz2 = vec2.size(); reverse(vec2.begin(), vec2.end()); rep(i, sz1) { vec.pb(vec1[i]); } rep(i, sz2) { vec.pb(vec2[i]); } pt w = vec[0]; int sz = vec.size(); for (int i = 1; i < sz; i++) { w = polacz(w, vec[i]); } return w; } pt query2(int l, int r) { vector<pt> vec1; vector<pt> vec2; l += MAXN; r += MAXN; while (l < r) { if (l % 2 == 1) { vec1.pb(seg2[l]); l++; } if (r % 2 == 0) { vec2.pb(seg2[r]); r--; } l /= 2; r /= 2; } if (l == r) { vec1.pb(seg2[l]); } vector<pt> vec; int sz1 = vec1.size(); int sz2 = vec2.size(); reverse(vec1.begin(), vec1.end()); rep(i, sz2) { vec.pb(vec2[i]); } rep(i, sz1) { vec.pb(vec1[i]); } pt w = vec[0]; int sz = vec.size(); for (int i = 1; i < sz; i++) { w = polacz(w, vec[i]); } return w; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; pt T[n - 1]; rep(i, n - 1) { cin >> T[i].l >> T[i].r; T[i].r--; T[i].czas = 1ll; T[i].travel = 0ll; upd(i, T[i]); upd2(i, T[i]); } while (q--) { int t; cin >> t; if (t == 2) { int a, c; ll b, d; cin >> a >> b >> c >> d; a--; c--; if (a < c) { pt w = query(a, c - 1); w = polacz({b, b, 0, 0}, w); ll ans = w.travel + max(0ll, w.czas + w.l - d); cout << ans << '\n'; } else if (a > c) { pt w = query2(c, a - 1); w = polacz({b, b, 0, 0}, w); ll ans = w.travel + max(0ll, w.czas + w.l - d); cout << ans << '\n'; } else { ll ans = max(0ll, b - d); cout << ans << '\n'; } } else { int p; ll l, r; cin >> p >> l >> r; p--; T[p].l = l; T[p].r = r - 1; T[p].czas = 1; T[p].travel = 0; upd(p, T[p]); upd2(p, T[p]); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...