oj.uz

Submission #712792

# Submission time Handle Problem Language Result Execution time Memory
712792 2023-03-20T02:37:42 Z PixelCat Bitaro, who Leaps through Time (JOI19_timeleap) C++14
4 / 100
 3 ms 468 KB 
/* nya */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
#define MOD (int)(1000000007)
// #define MOD (int)(998244353)
using namespace std;
using LL = long long;
// using LLL = __int128_t;
using pii = pair<int, int>;
 
#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#endif

struct Nyacho {
    int typ, l, r, cost;
};
ostream& operator<<(ostream& os, const Nyacho nya) {
    if(nya.typ) cout << nya.l << "->" << nya.r << " (" << nya.cost << ")";
    else        cout << nya.l << "::" << nya.r << " (" << nya.cost << ")";
    return os;
}

#define dist(x, l, r) max(0ll, (x) - (r))
#define clamp(x, l, r) max(l, min(r, x))
Nyacho merge(const Nyacho &a, const Nyacho &b) {
    Nyacho c;
    if(a.typ == 0 && b.typ == 0) {
        if(min(a.r, b.r) < max(a.l, b.l)) {
            if(a.r < b.r) c = {1, a.r, b.l, 0};
            else          c = {1, a.l, b.r, a.l - b.r};
        } else {
            c = {0, max(a.l, b.l), min(a.r, b.r), 0};
        }
    } else if(a.typ == 0) {
        c = {1, clamp(b.l, a.l, a.r), b.r, max(0ll, a.l - b.l)};
    } else if(b.typ == 0) {
        c = {1, a.l, clamp(a.r, b.l, b.r), max(0ll, a.r - b.r)};
    } else {
        c = {1, a.l, b.r, max(0ll, a.r - b.l)};
    }
    c.cost += a.cost + b.cost;
    return c;
}

const int MAXN = 300030;

Nyacho nya[MAXN];
Nyacho ayn[MAXN];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    int n, q; cin >> n >> q;
    assert(max(n, q) <= 1000);
    For(i, 1, n - 1) {
        int l, r; cin >> l >> r; r--;
        nya[i] = {0, l - i, r - i, 0};
        ayn[i] = {0, l + i, r + i, 0};
        //cout << nya[i] << " " << ayn[i] << "\n";
    }
    while(q--) {
        int op; cin >> op;
        if(op == 1) {
            int p, s, e; cin >> p >> s >> e; e--;
            nya[p] = {0, s - p, e - p, 0};
            ayn[p] = {0, s + p, e + p, 0};
        } else {
            int a, b, c, d; cin >> a >> b >> c >> d;
            Nyacho res;
            if(a < c) {
                c--; b -= a; d -= c + 1;
                res = {0, b, b, 0};
                For(i, a, c) {
                    res = merge(res, nya[i]);
                    //cout << res << "\n";
                }
            } else {
                a--; b += a; d += c - 1;
                res = {0, b, b, 0};
                Forr(i, a, c) {
                    res = merge(res, ayn[i]);
                    //cout << res << "\n";
                }
            }
            res = merge(res, {0, d, d, 0});
            cout << res.cost << "\n";
        }
    }
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 1 ms 400 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 408 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 2 ms 340 KB Output is correct
34 Correct 2 ms 340 KB Output is correct
35 Correct 2 ms 340 KB Output is correct
36 Correct 2 ms 340 KB Output is correct
37 Correct 2 ms 340 KB Output is correct
38 Correct 2 ms 340 KB Output is correct
39 Correct 2 ms 340 KB Output is correct
40 Correct 2 ms 368 KB Output is correct
41 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 1 ms 400 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 408 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 2 ms 340 KB Output is correct
34 Correct 2 ms 340 KB Output is correct
35 Correct 2 ms 340 KB Output is correct
36 Correct 2 ms 340 KB Output is correct
37 Correct 2 ms 340 KB Output is correct
38 Correct 2 ms 340 KB Output is correct
39 Correct 2 ms 340 KB Output is correct
40 Correct 2 ms 368 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Runtime error 1 ms 468 KB Execution killed with signal 6
43 Halted 0 ms 0 KB -