Submission #757261

#TimeUsernameProblemLanguageResultExecution timeMemory
757261hulahula3247Bitaro, who Leaps through Time (JOI19_timeleap)C++17
0 / 100
533 ms102828 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; #define all(v) v.begin(), v.end() const ll INF = 0x3f3f3f3f; ll N, Q; struct Node { ll L, R, P, T; Node operator+(const Node &rhs) const { Node ret; ret.L = min(max(L, rhs.L), rhs.R); ret.R = max(min(R, rhs.R), rhs.L); ret.P = max(P, rhs.P); ret.T = T + rhs.T + max(ll(0), (min(P, ret.L)-L)); return ret; } }; struct Seg { Node tree[1200050]; Node arr[300050]; void b1(ll n, ll s, ll e) { if (s == e) { tree[n] = arr[s]; return; } ll m = (s+e)/2; b1(2*n, s, m); b1(2*n+1, m+1, e); tree[n] = tree[2*n] + tree[2*n+1]; } void u1(ll n, ll s, ll e, ll idx, ll l, ll r) { if (s == e) { tree[n] = {l, r, l, 0}; return; } ll m = (s+e)/2; if (idx <= m) u1(2*n, s, m, idx, l, r); else u1(2*n+1, m+1, e, idx, l, r); tree[n] = tree[2*n] + tree[2*n+1]; } Node q1(ll n, ll s, ll e, ll l, ll r) { if (l <= s && e <= r) return tree[n]; if (s > r || e < l) return {-1, INF, -1, 0}; ll m = (s+e)/2; return q1(2*n, s, m, l, r) + q1(2*n+1, m+1, e, l, r); } ll q2(ll x1, ll x2, ll t1, ll t2) { Node start = {t1, t1, t1, 0}; Node end = {t2, t2, t2, 0}; Node mid = q1(1, 0, N-1, x1, x2); Node ret = (start + mid) + end; return ret.T + max(ll(0), ret.P-ret.L); } }seg1, seg2; void solve() { cin >> N >> Q; N--; for (int i = 0; i < N; i++) { ll l, r; cin >> l >> r; seg1.arr[i] = {N-1-i+l, N-2-i+r, N-1-i+l, 0}; seg2.arr[N-1-i] = {l+i, r+i-1, l+i, 0}; } seg1.b1(1, 0, N-1); seg2.b1(1, 0, N-1); for (int i = 0; i < Q; i++) { int t; cin >> t; if (t == 1) { ll a, b, c; cin >> a >> b >> c; a -= 1; seg1.u1(1, 0, N-1, a, N-1-a+b, N-2-a+c); seg2.u1(1, 0, N-1, N-1-a, a+b, a-1+c); } else { ll x1, t1, x2, t2; cin >> x1 >> t1 >> x2 >> t2; bool fg = 0; if (x1 > x2) { fg = 1; swap(x1, x2); x1 -= 1; x2 -= 2; x1 = N-1-x1; x2 = N-1-x2; swap(x1, x2); } else { x1 -= 1; x2 -= 2; } t1 += N-1-x1; t2 += N-2-x2; if (!fg) cout << seg1.q2(x1, x2, t1, t2) << '\n'; else cout << seg2.q2(x1, x2, t1, t2) << '\n'; } } } int main(void) { ios::sync_with_stdio(false); cin.tie(0); int T = 1; //cin >> T; while (T--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...