oj.uz

Submission #796814

# Submission time Handle Problem Language Result Execution time Memory
796814 2023-07-28T19:12:12 Z RushB Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 415 ms 524288 KB 
//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;
        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

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;
      |                 ~~^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 608 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 668 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 2 ms 596 KB Output is correct
23 Correct 1 ms 656 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 2 ms 600 KB Output is correct
32 Correct 2 ms 552 KB Output is correct
33 Correct 2 ms 596 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 2 ms 600 KB Output is correct
39 Correct 2 ms 600 KB Output is correct
40 Correct 2 ms 596 KB Output is correct
41 Runtime error 246 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 88992 KB Output is correct
2 Correct 375 ms 70656 KB Output is correct
3 Correct 386 ms 70992 KB Output is correct
4 Correct 382 ms 70448 KB Output is correct
5 Correct 387 ms 104084 KB Output is correct
6 Correct 387 ms 96888 KB Output is correct
7 Correct 391 ms 104096 KB Output is correct
8 Correct 400 ms 105156 KB Output is correct
9 Correct 371 ms 70860 KB Output is correct
10 Correct 390 ms 104268 KB Output is correct
11 Correct 412 ms 104160 KB Output is correct
12 Correct 395 ms 104908 KB Output is correct
13 Correct 398 ms 105056 KB Output is correct
14 Runtime error 224 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 608 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 668 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 2 ms 596 KB Output is correct
23 Correct 1 ms 656 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 2 ms 600 KB Output is correct
32 Correct 2 ms 552 KB Output is correct
33 Correct 2 ms 596 KB Output is correct
34 Correct 2 ms 596 KB Output is correct
35 Correct 2 ms 596 KB Output is correct
36 Correct 2 ms 596 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 2 ms 600 KB Output is correct
39 Correct 2 ms 600 KB Output is correct
40 Correct 2 ms 596 KB Output is correct
41 Runtime error 246 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -