Submission #796821

#TimeUsernameProblemLanguageResultExecution timeMemory
796821RushBBitaro, who Leaps through Time (JOI19_timeleap)C++17
100 / 100
669 ms104268 KiB
//besmellah //mage mikhad chi beshe? #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define int long long const int64_t INF = 1ll << 60; const int N = 3e5 + 50; int n, q, A[N], B[N], C[N], D[N], P[N], t[N], L[N], R[N], query_ans[N]; struct node { int mxl, mnr, fil, fir, ansl, ansr, locl, locr; }; int dist(int l, int r) { return max(r - l, 0ll); } void calc(node x, int l, int &rel, int &reans) { if (x.mxl <= x.mnr) { rel = min(max(l, x.mxl), x.mnr); reans += dist(rel, l); } else { int dl = dist(x.fil, l) + x.ansl; int dr = dist(x.fir, l) + x.ansr; if (dl < dr) { reans += dl; rel = x.locl; } else { reans += dr; rel = x.locr; } } } node operator +(node l, node r) { node R; R.mxl = max(l.mxl, r.mxl); R.mnr = min(l.mnr, r.mnr); if (R.mxl <= R.mnr) { R.ansl = R.ansr = 0; R.locl = R.mxl; R.locr = R.mnr; R.fil = R.mxl; R.fir = R.mnr; return R; } R.fil = max(l.fil, r.fil); R.fir = min(l.fir, r.fir); if (l.mxl > l.mnr || R.fil > R.fir) { R.fil = l.fil; R.fir = l.fir; } R.ansl = R.ansr = 0; int tl, tr; calc(l, R.fil, tl, R.ansl); calc(r, tl, R.locl, R.ansl); calc(l, R.fir, tr, R.ansr); calc(r, tr, R.locr, R.ansr); return R; } node seg[N << 2]; //int mxl, mnr, fil, fir, ansl, ansr, locl, locr; void build(int v, int l, int r) { if (l + 1 == r) { seg[v] = {L[l], R[l], L[l], R[l], 0, 0, L[l], R[l]}; return; } int m = l + r >> 1; build(v << 1, l, m); build(v << 1 | 1, m, r); seg[v] = seg[v << 1] + seg[v << 1 | 1]; } void update(int v, int l, int r, int ind, int L, int R) { if (l + 1 == r) { seg[v] = {L, R, L, R, 0, 0, L, R}; return; } int m = l + r >> 1; if (ind < m) update(v << 1, l, m, ind, L, R); else update(v << 1 | 1, m, r, ind, L, R); seg[v] = seg[v << 1] + seg[v << 1 | 1]; } //void calc(node x, int l, int &rel, int &reans) { void get(int v, int l, int r, int L, int R, int &time, int &re) { if (L <= l && r <= R) { calc(seg[v], time, time, re); return; } int m = l + r >> 1; if (R <= m) get(v << 1, l, m, L, R, time, re); else if (L >= m) get(v << 1 | 1, m, r, L, R, time, re); else { get(v << 1, l, m, L, R, time, re); get(v << 1 | 1, m, r, L, R, time, re); } } void solve() { FOR(i, 1, n) { L[i] -= i; R[i] -= i + 1; } build(1, 1, n); FOR(i, 0, q) { B[i] -= (t[i] == 1 ? P[i] : A[i]); D[i] -= (t[i] == 1 ? P[i] + 1 : C[i]); if (t[i] == 1) { update(1, 1, n, P[i], B[i], D[i]); } else if (C[i] > A[i]) { int time = B[i]; get(1, 1, n, A[i], C[i], time, query_ans[i]); query_ans[i] += dist(D[i], time); } else if (C[i] == A[i]) query_ans[i] = dist(D[i], B[i]); } FOR(i, 1, n) { L[i] += i; R[i] += i + 1; } FOR(i, 0, q) { B[i] += (t[i] == 1 ? P[i] : A[i]); D[i] += (t[i] == 1 ? P[i] + 1 : C[i]); } } signed main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> q; if (n == 1) { while (q--) { int t, a, b, c, d; cin >> t >> a >> b >> c >> d; cout << dist(d, b) << '\n'; } return 0; } FOR(i, 1, n) cin >> L[i] >> R[i]; FOR(i, 0, q) { cin >> t[i]; if (t[i] == 1) { cin >> P[i] >> B[i] >> D[i]; } else { cin >> A[i] >> B[i] >> C[i] >> D[i]; } } solve(); reverse(L + 1, L + n); reverse(R + 1, R + n); FOR(i, 0, q) { if (t[i] == 1) { P[i] = n - P[i]; } else { A[i] = n + 1 - A[i]; C[i] = n + 1 - C[i]; } } solve(); FOR(i, 0, q) if (t[i] == 2) { cout << query_ans[i] << '\n'; } return 0; } //19:33:34

Compilation message (stderr)

timeleap.cpp: In function 'void build(long long int, long long int, long long int)':
timeleap.cpp:71:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int m = l + r >> 1;
      |                 ~~^~~
timeleap.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:81:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int m = l + r >> 1;
      |                 ~~^~~
timeleap.cpp: In function 'void get(long long int, long long int, long long int, long long int, long long int, long long int&, long long int&)':
timeleap.cpp:94:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int m = l + r >> 1;
      |                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...