Submission #1190543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190543		onbert	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	3094 ms	68288 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node {
    int type, sz;
    ll cost;
    int inl, inr, outl, outr;
};
node nul = {0, 0, 0, 0, 0, 0, 0};
node merge(node &x, node &y) {
    if (x.type == 0) return y;
    if (y.type == 0) return x;
    node ret;
    ret.sz = x.sz + y.sz;
    ret.type = max(x.type, y.type);
    ret.cost = x.cost + y.cost;
    if (x.type == 1 && y.type == 2) {
        ret.outr = y.outr;
        if (x.outr < y.inr) ret.inr = x.inr;
        else if (x.outl > y.inr) ret.inr = x.inl, ret.cost += x.outl - y.inr;
        else ret.inr = y.inr - x.sz;
    } else if (x.type == 2 && y.type == 1) {
        ret.inr = x.inr;
        if (y.inl > x.outr) ret.outr = y.outl;
        else if (y.inr < x.outr) ret.outr = y.outr, ret.cost += x.outr - y.inr;
        else ret.outr = x.outr + y.sz;
    } else if (x.type == 2 && y.type == 2) {
        ret.inr = x.inr, ret.outr = y.outr;
        ret.cost += max(x.outr - y.inr, (int)0);
    } else if (x.type == 1 && y.type == 1) {
        if (x.outr < y.inl) ret.type = 2, ret.inr = x.inr, ret.outr = y.outl;
        else if (x.outl > y.inr) ret.type = 2, ret.inr = x.inl, ret.outr = y.outr, ret.cost += x.outl - y.inr;
        else {
            int l = max(x.outl, y.inl), r = min(x.outr, y.inr);
            ret.inl = l - x.sz, ret.inr = r - x.sz;
            ret.outl = l + y.sz, ret.outr = r + y.sz;
        }
    }
    if (ret.type == 2) ret.inl = ret.inr, ret.outl = ret.outr;
    return ret;
}

const int maxn = 3e5 + 5, maxN = 1.2e6 + 5;
int n;
pair<int,int> a[maxn];

int dir[2] = {1, -1};
node seg[maxN][2];

void build(int id, int l, int r, int i) {
    // if (id != 0) cout << id << " " << l << " " << r << " " << i << endl;
    // if (i == 0) assert(id < maxN);
    if (l == r) {
        // cout << l << " " << l * dir[i] << endl;
        pair<int,int> cur = a[l * dir[i]];
        seg[id][i] = {1, 1, 0, cur.first, cur.second, cur.first+1, cur.second+1};
        return;
    }
    int mid = (l+r)/2;
    if (i == 1) mid = (l+r-1)/2;
    assert(mid+1 != l);
    build(id*2, l, mid, i); build(id*2+1, mid+1, r, i);
    seg[id][i] = merge(seg[id*2][i], seg[id*2+1][i]);
}
void update(int id, int l, int r, int target, int i) {
    if (r < target || target < l) return;
    if (l == r) {
        pair<int,int> cur = a[l * dir[i]];
        seg[id][i] = {1, 1, 0, cur.first, cur.second, cur.first+1, cur.second+1};
        return;
    }
    int mid = (l+r)/2;
    if (i == 1) mid = (l+r-1)/2;
    update(id*2, l, mid, target, i); update(id*2+1, mid+1, r, target, i);
    seg[id][i] = merge(seg[id*2][i], seg[id*2+1][i]);
}
node qry(int id, int l, int r, int findl, int findr, int i) {
    if (r < findl || findr < l) return nul;
    if (findl <= l && r <= findr) return seg[id][i];
    int mid = (l+r)/2;
    if (i == 1) mid = (l+r-1)/2;
    node lhs = qry(id*2, l, mid, findl, findr, i);
    node rhs = qry(id*2+1, mid+1, r, findl, findr, i);
    return merge(lhs, rhs);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int q;
    cin >> n >> q;
    n--;
    for (int i=1;i<=n;i++) {
        cin >> a[i].first >> a[i].second;
        a[i].second--;
    }
    build(1, 1, n, 0);
    // build(1, -n, -1, 1);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, l, r;
            cin >> x >> l >> r;
            r--;
            a[x] = {l, r};

            update(1, 1, n, x, 0);
            update(1, -n, -1, -x, 1);

        } else if (t == 2) {
            int l, intt, r, outt;
            cin >> l >> intt >> r >> outt;
            if (l == r) {
                cout << max(intt - outt, (int)0) << "\n";
                continue;
            }

            node cur = nul;

            if (l < r) cur = qry(1, 1, n, l, r-1, 0);
            else cur = qry(1, -n, -1, -(l-1), -r, 1);

            cur = nul;
            if (l < r) {
                for (int i=l;i<=r-1;i++) {
                    node x = {1, 1, 0, a[i].first, a[i].second, a[i].first+1, a[i].second+1};
                    cur = merge(cur, x);
                }
            } else {
                for (int i=l-1;i>=r;i--) {
                    node x = {1, 1, 0, a[i].first, a[i].second, a[i].first+1, a[i].second+1};
                    cur = merge(cur, x);
                }
            }

            ll ans = cur.cost;
            if (cur.type == 2) ans += max(intt - cur.inr, (int)0) + max(cur.outr - outt, (int)0);
            else {
                if (intt < cur.inl) intt = cur.inl;
                else if (intt > cur.inr) ans += intt - cur.inr, intt = cur.inr;
                intt += cur.sz;
                ans += max(intt - outt, (int)0);
            }
            // cout << cur.type << " " << cur.inl << " " << cur.inr << " " << cur.sz << endl;
            cout << ans << "\n";
        }
    }
}

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