Submission #712791

#	Time	Username	Problem	Language	Result	Execution time	Memory
712791		PixelCat	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	1 ms	468 KiB

timeleap

/* 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};
        } 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: 0 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66