Submission #1164919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164919		OI_Account	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	423 ms	589824 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct detail {
    int type;
    ll q, x, y;
    ll l, r;
    void init(int t, ll a, ll b, ll c) {
        type = t;
        if (t == 1) {
            q = a;
            x = b;
            y = c;
        }
        else {
            l = a;
            r = b;
        }
    }
    pair<ll, ll> get(ll p) {
        if (type == 0) {
            if (p <= l)
                return {0, l};
            if (p <= r)
                return {0, p};
            return {p - r, r};
        }
        return {x + max(0ll, p - q), y};
    }
};

const int N = 300'000;

int n, q;
ll l[N + 10], r[N + 10];
detail seg[2][4 * N + 10];
pair<ll, ll> p[2][N + 10];

void readInput() {
    cin >> n >> q;
    for (int i = 1; i < n; i++)
        cin >> l[i] >> r[i];
}

inline detail getDetail(int t, ll a, ll b, ll c = 0) {
    detail res;
    res.init(t, a, b, c);
    return res;
}

detail operator+(detail a, detail b) {
    if (a.type == -1)
        return b;
    if (b.type == -1)
        return a;
    if (a.type == 0 && b.type == 1) {
        if (a.r < b.q)
            return getDetail(1, a.r, b.x, b.y);
        if (a.l <= b.q)
            return getDetail(1, b.q, b.x, b.y);
        return getDetail(1, a.l, b.get(a.l).first, b.y);
    }
    if (a.type) {
        pair<ll, ll> p = b.get(a.y);
        return getDetail(1, a.q, a.x + p.first, p.second);
    }
    if (a.r <= b.l)
        return getDetail(1, a.r, 0, b.l);
    if (b.r <= a.l)
        return getDetail(1, a.l, b.get(a.l).first, b.r);
    return getDetail(0, max(a.l, b.l), min(a.r, b.r));
}

detail get(int t, int st, int en, int id = 1, int l = 1, int r = n) {
    if (en <= l || r <= st)
        return getDetail(-1, 0, 0);
    if (st <= l && r <= en)
        return seg[t][id];
    int mid = (l + r) >> 1;
    return get(t, st, en, id << 1, l, mid) + get(t, st, en, id << 1 | 1, mid, r);
}

void update(int t, int idx, pair<ll, ll> p, int id = 1, int l = 1, int r = n) {
    if (idx < l || r <= idx)
        return;
    if (l + 1 == r) {
        seg[t][id] = getDetail(0, p.first - l, p.second - l);
        return;
    }
    int mid = (l + r) >> 1;
    update(t, idx, p, id << 1, l, mid);
    update(t, idx, p, id << 1 | 1, mid, r);
    seg[t][id] = seg[t][id << 1] + seg[t][id << 1 | 1];
}

void build(int t, int id = 1, int l = 1, int r = n) {
    if (l + 1 == r) {
        seg[t][id] = getDetail(0, p[t][l].first - l, p[t][l].second - l);
        return;
    }
    int mid = (l + r) >> 1;
    build(t, id << 1, l, mid);
    build(t, id << 1 | 1, mid, r);
    seg[t][id] = seg[t][id << 1] + seg[t][id << 1 | 1];
}

void build() {
    for (int i = 1; i < n; i++)
        p[0][i] = p[1][n - i] = {l[i], r[i] - 1};
    build(0);
    build(1);
}

void qeuryChange() {
    ll p, l, r;
    cin >> p >> l >> r;
    update(0, p, {l, r - 1});
    update(1, n - p, {l, r - 1});
}

void queryGet() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a == c)
        cout << max(0ll, b - d) << '\n';
    else if (a < c) {
        b -= a;
        d -= c;
        detail dt = get(0, a, c);
        pair<ll, ll> p = dt.get(b);
        cout << p.first + max(0ll, p.second - d) << '\n';
    }
    else {
        a = n - a + 1;
        b -= a;
        c = n - c + 1;
        d -= c;
        detail dt = get(1, a, c);
        pair<ll, ll> p = dt.get(b);
        cout << p.first + max(0ll, p.second - d) << '\n';
    }
}

void query() {
    int type;
    cin >> type;
    if (type == 1)
        qeuryChange();
    else
        queryGet();
}

void solve() {
    while (q--)
        query();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    build();
    solve();
    return 0;
}

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