제출 #712793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712793		PixelCat	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	4 / 100	2 ms	488 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 clamp(x, l, r) max(l, min(r, x))
Nyacho operator+(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;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    Nyacho nya[MAXN << 2];
    Nyacho ayn[MAXN << 2];
    void upd(int id, int l, int r, int i, int L, int R) {
        if(l == r) {
            nya[id] = {0, L - i, R - i, 0};
            ayn[id] = {0, L + i, R + i, 0};
            return;
        }
        int m = (l + r) / 2;
        if(i <= m) upd(L(id), l, m, i, L, R);
        else upd(R(id), m + 1, r, i, L, R);
        nya[id] = (nya[L(id)] + nya[R(id)]);
        ayn[id] = (ayn[R(id)] + ayn[L(id)]);
    }
    Nyacho qry_lr(int id, int l, int r, int L, int R) {
        if(l >= L && r <= R) return nya[id];
        int m = (l + r) / 2;
        if(R <= m) return qry_lr(L(id), l, m, L, R);
        if(L > m)  return qry_lr(R(id), m + 1, r, L, R);
        return (qry_lr(L(id), l, m, L, R) + qry_lr(R(id), m + 1, r, L, R));
    }
    Nyacho qry_rl(int id, int l, int r, int L, int R) {
        if(l >= L && r <= R) return ayn[id];
        int m = (l + r) / 2;
        if(R <= m) return qry_rl(L(id), l, m, L, R);
        if(L > m)  return qry_rl(R(id), m + 1, r, L, R);
        return (qry_rl(R(id), m + 1, r, L, R) + qry_rl(L(id), l, m, L, R));
    }
} seg;

// 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--;
        seg.upd(0, 1, n - 1, i, l, 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--;
            seg.upd(0, 1, n - 1, p, s, 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;
            if(a == c) {
                cout << max(0ll, b - d) << "\n";
                continue;
            }
            Nyacho res;
            if(a < c) {
                c--; b -= a; d -= c + 1;
                res = (Nyacho){0, b, b, 0} + seg.qry_lr(0, 1, n - 1, a, c);
                // For(i, a, c) {
                //     res = merge(res, nya[i]);
                //     //cout << res << "\n";
                // }
            } else {
                a--; b += a; d += c - 1;
                res = (Nyacho){0, b, b, 0} + seg.qry_rl(0, 1, n - 1, c, a);
                // Forr(i, a, c) {
                //     res = merge(res, ayn[i]);
                //     //cout << res << "\n";
                // }
            }
            res = (res + (Nyacho){0, d, d, 0});
            cout << res.cost << "\n";
        }
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66