Submission #1165331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165331		OI_Account	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	743 ms	112164 KiB

timeleap

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

#define type2 first.first
#define q2 first.second
#define x second.first
#define y second.second
#define l2 first.second
#define r2 second.first

typedef __int128 ll;
typedef long long ll2;
typedef pair<pair<int, ll>, pair<ll, ll>> detail;

pair<ll, ll> getP(detail &b, ll p) {
    if (b.type2 == 0) {
        if (p <= b.l2)
            return {0, b.l2};
        if (p <= b.r2)
            return {0, p};
        return {p - b.r2, b.r2};
    }
    return {b.x + max((ll) 0, p - b.q2), b.y};
}

const int N = 300'000;

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

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

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

detail operator+(detail a, detail b) {
    if (a.type2 == -1)
        return b;
    if (b.type2 == -1)
        return a;
    if (a.type2 == 0 && b.type2 == 1) {
        if (a.r2 < b.q2)
            return getDetail(1, a.r2, b.x, b.y);
        if (a.l2 <= b.q2)
            return getDetail(1, b.q2, b.x, b.y);
        return getDetail(1, a.l2, getP(b, a.l2).first, b.y);
    }
    if (a.type2) {
        pair<ll, ll> p = getP(b, a.y);
        return getDetail(1, a.q2, a.x + p.first, p.second);
    }
    if (a.r2 <= b.l2)
        return getDetail(1, a.r2, 0, b.l2);
    if (b.r2 <= a.l2)
        return getDetail(1, a.l2, getP(b, a.l2).first, b.r2);
    return getDetail(0, max(a.l2, b.l2), min(a.r2, b.r2));
}

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][ids[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][ids[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][ids[id]] = seg[t][ids[id << 1]] + seg[t][ids[id << 1 | 1]];
}

void build(int t, int id = 1, int l = 1, int r = n) {
    if (l + 1 == r) {
        seg[t][ids[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][ids[id]] = seg[t][ids[id << 1]] + seg[t][ids[id << 1 | 1]];
}

int counter;

void calcIds(int id = 1, int l = 1, int r = n) {
    ids[id] = ++counter;
    if (l + 1 == r)
        return;
    int mid = (l + r) >> 1;
    calcIds(id << 1, l, mid);
    calcIds(id << 1 | 1, mid, r);
}

void build() {
    calcIds();
    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() {
    ll2 p, l, r;
    cin >> p >> l >> r;
    update(0, p, {l, r - 1});
    update(1, n - p, {l, r - 1});
}

void queryGet() {
    ll2 a2, b2, c2, d2;
    cin >> a2 >> b2 >> c2 >> d2;
    ll a = a2, b = b2, c = c2, d = d2;
    if (a == c)
        cout << (ll2) max((ll) 0, b - d) << '\n';
    else if (a < c) {
        b -= a;
        d -= c;
        detail dt = get(0, a, c);
        pair<ll, ll> p = getP(dt, b);
        cout << (ll2) (p.first + max((ll) 0, 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 = getP(dt, b);
        cout << (ll2) (p.first + max((ll) 0, 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();
    if (n != 1)
        build();
    solve();
    return 0;
}

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