Submission #1165005

#TimeUsernameProblemLanguageResultExecution timeMemory
1165005OI_AccountBitaro, who Leaps through Time (JOI19_timeleap)C++20
0 / 100
417 ms60336 KiB
#include <bits/stdc++.h> using namespace std; #define type2 first.first #define q2 first.second #define x second.first #define y second.second #define l2 first.second #define r2 second.first typedef long long ll; typedef pair<pair<int, ll>, pair<ll, ll>> detail; pair<ll, ll> getP(detail &b, ll p) { if (b.type2 == 0) { if (p <= b.l2) return {0, b.l2}; if (p <= b.r2) return {0, p}; return {p - b.r2, b.r2}; } return {b.x + max(0ll, p - b.q2), b.y}; } const int N = 300'000; int n, q, ids[4 * N + 10]; ll l[N + 10], r[N + 10]; detail seg[2][2 * N + 10]; pair<ll, ll> p[2][N + 10]; void readInput() { cin >> n >> q; for (int i = 1; i < n; i++) cin >> l[i] >> r[i]; } inline detail getDetail(int t, ll a, ll b, ll c = 0) { detail res; res = {{t, a}, {b, c}}; return res; } detail operator+(detail a, detail b) { if (a.type2 == -1) return b; if (b.type2 == -1) return a; if (a.type2 == 0 && b.type2 == 1) { if (a.r2 < b.q2) return getDetail(1, a.r2, b.x, b.y); if (a.l2 <= b.q2) return getDetail(1, b.q2, b.x, b.y); return getDetail(1, a.l2, getP(b, a.l2).first, b.y); } if (a.type2) { pair<ll, ll> p = getP(b, a.y); return getDetail(1, a.q2, a.x + p.first, p.second); } if (a.r2 <= b.l2) return getDetail(1, a.r2, 0, b.l2); if (b.r2 <= a.l2) return getDetail(1, a.l2, getP(b, a.l2).first, b.r2); return getDetail(0, max(a.l2, b.l2), min(a.r2, b.r2)); } detail get(int t, int st, int en, int id = 1, int l = 1, int r = n) { if (en <= l || r <= st) return getDetail(-1, 0, 0); if (st <= l && r <= en) return seg[t][ids[id]]; int mid = (l + r) >> 1; return get(t, st, en, id << 1, l, mid) + get(t, st, en, id << 1 | 1, mid, r); } void update(int t, int idx, pair<ll, ll> p, int id = 1, int l = 1, int r = n) { if (idx < l || r <= idx) return; if (l + 1 == r) { seg[t][ids[id]] = getDetail(0, p.first - l, p.second - l); return; } int mid = (l + r) >> 1; update(t, idx, p, id << 1, l, mid); update(t, idx, p, id << 1 | 1, mid, r); seg[t][ids[id]] = seg[t][ids[id << 1]] + seg[t][ids[id << 1 | 1]]; } void build(int t, int id = 1, int l = 1, int r = n) { if (l + 1 == r) { seg[t][ids[id]] = getDetail(0, p[t][l].first - l, p[t][l].second - l); return; } int mid = (l + r) >> 1; build(t, id << 1, l, mid); build(t, id << 1 | 1, mid, r); seg[t][ids[id]] = seg[t][ids[id << 1]] + seg[t][ids[id << 1 | 1]]; } int counter; void calcIds(int id = 1, int l = 1, int r = n) { ids[id] = ++counter; if (l + 1 == r) return; int mid = (l + r) >> 1; calcIds(id << 1, l, mid); calcIds(id << 1 | 1, mid, r); } void build() { calcIds(); for (int i = 1; i < n; i++) p[0][i] = p[1][n - i] = {l[i], r[i] - 1}; build(0); build(1); } void qeuryChange() { ll p, l, r; cin >> p >> l >> r; update(0, p, {l, r - 1}); update(1, n - p, {l, r - 1}); } void queryGet() { ll a, b, c, d; cin >> a >> b >> c >> d; if (a == c) cout << max(0ll, b - d) << '\n'; else if (a < c) { b -= a; d -= c; detail dt = get(0, a, c); pair<ll, ll> p = getP(dt, b); cout << p.first + max(0ll, p.second - d) << '\n'; } else { a = n - a + 1; b -= a; c = n - c + 1; d -= c; detail dt = get(1, a, c); pair<ll, ll> p = getP(dt, b); cout << p.first + max(0ll, p.second - d) << '\n'; } } void query() { int type; cin >> type; if (type == 1) qeuryChange(); else queryGet(); } void solve() { while (q--) query(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); readInput(); build(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...