Submission #1173074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173074		patgra	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	357 ms	62500 KiB

timeleap

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back
#define int ll

using namespace std;

constexpr int inf = 2e18;

vector<pair<int, pair<int, int>>> t, tRev;  //  Either {-1, {l, r}}  or  {Cost inside, {Start, End}}
int tB;
int n, q;
int squirt;
vector<pair<int, int>> arr, arrRev;

bool verbose = 1;

string skull(int x) {
    if(x == inf) return "+oo";
    if(x == -inf) return "-oo";
    stringstream ss;
    ss << x;
    return ss.str();
}

int passThrough(pair<int, pair<int, int>> comb, int startH, int endH) {
    if(verbose) DC << "PassThrough( {" << skull(comb.first) << ' ' << skull(comb.second.first) << ' ' << skull(comb.second.second) << "} " << startH << ' ' << endH << " )  ->  ";
    if(comb.first == -1) {
        int myCost = 0;
        auto [cl, cr] = comb.second;
        if(startH > cr) myCost += startH - cr, startH = cr;
        if(startH < cl) startH = cl;
        if(startH > endH) myCost += startH - endH;
        if(verbose) DC << myCost << eol;
        return myCost;
    }
    int myCost = comb.first;
    auto [cs, ce] = comb.second;
    if(startH > cs) myCost += startH - cs;
    if(ce > endH) myCost += ce - endH;
    if(verbose) DC << myCost << eol;
    return myCost;
}

pair<int, pair<int, int>> combineXD(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    auto [ca, lra] = a;
    auto [cb, lrb] = b;
    auto [la, ra] = lra;
    auto [lb, rb] = lrb;
    if(ca == -1) {
        if(cb == -1) {
            auto maxl = max(la, lb);
            auto minr = min(ra, rb);
            if(maxl <= minr) return {-1, {maxl, minr}};
            if(maxl == la) return {maxl - minr, {maxl, minr}};
            return {0, {minr, maxl}};
        }
        return {cb + max(0ll, la - lb), {min(max(lb, la), ra), rb}};
    }
    if(cb == -1) return {ca + max(0ll, ra - rb), {la, min(max(ra, lb), rb)}};
    return {ca + cb + max(0ll, ra - lb), {la, rb}};
}

pair<int, pair<int, int>> combine(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    auto c = combineXD(a, b);
    DEBUG {
        verbose = false;
        DC << "  Combine( {" << skull(a.first) << ' ' << skull(a.second.first) << ' ' << skull(a.second.second) << "} ; {" << skull(b.first) << ' ' << skull(b.second.first) << ' ' << skull(b.second.second) << "} )  ";
        DC << "-->  { " << skull(c.first) << ' ' << skull(c.second.first) << ' ' << skull(c.second.second) << "}" << eol;
        rep(i, -10ll, 10) rep(j, -10ll, 10) {
            auto costc = passThrough(c, i, j);
            auto mid = (a.first == -1 ? min(max(i, a.second.first), a.second.second) : a.second.second);
            assert(costc == (passThrough(a, i, mid) + passThrough(b, mid, j)));
        }
        verbose = true;
    }
    return c;
}

void tMod(int i, int l, int r, bool Rev) {
    DC << "tMod( " << i << ' ' << l << ' ' << r << ' ' << Rev << " )" << eol;
    if(Rev) swap(t, tRev);
    i += tB;
    t[i] = {-1, {l, r}};
    i /= 2;
    while(i) t[i] = combine(t[i * 2], t[i * 2 + 1]), i /= 2;
    if(Rev) swap(t, tRev);
}

pair<int, pair<int, int>> tQuery(int l, int r, bool Rev) {
    DC << "tQ( " << l << ' ' << r << ' ' << Rev << " )" << eol;
    if(Rev) swap(t, tRev);
    l += tB; r += tB;
    auto leftComb = t[l], rightComb = t[r];
    while(l / 2 != r / 2) {
        if(l % 2 == 0) leftComb = combine(leftComb, t[l + 1]);
        if(r % 2 == 1) rightComb = combine(t[r - 1], rightComb);
        l /= 2, r /= 2;
    }
    if(Rev) swap(t, tRev);
    auto ret = combine(leftComb, rightComb);
    DC << "-> " << skull(ret.first) << ' ' << skull(ret.second.first) << ' ' << skull(ret.second.second) << eol;
    return ret;
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    n--;
    tB = 1 << (32 - __builtin_clz(n - 1));
    DC << n << ' ' << tB << eol;
    arr.resize(n), arrRev.resize(n);
    t.resize(tB * 2, {-1, {-inf, inf}}), tRev.resize(tB * 2, {-1, {-inf, inf}});
    rep(i, 0, n) {
        int l, r;
        cin >> l >> r;
        r--;
        l -= i, r -= i;
        arr[i] = {l, r};
        tMod(i, l, r, 0);
        l += i, r += i;
        l -= n - 1 - i, r -= n - 1 - i;
        arrRev[n - 1 - i] = {l, r};
        tMod(n - 1 - i, l, r, 1);
    }

    rep(_, 0, q) {
        int type;
        cin >> type;
        if(type == 1) {
            int i, l, r;
            cin >> i >> l >> r;
            i--;
            r--;
            l -= i, r -= i;
            arr[i] = {l, r};
            tMod(i, l, r, 0);
            l += i, r += i;
            l -= n - 1 - i, r -= n - 1 - i;
            arrRev[n - 1 - i] = {l, r};
            tMod(n - 1 - i, l, r, 1);
            continue;
        }
        int l, tl, r, tr;
        cin >> l >> tl >> r >> tr;
        l--, r--;
        if(l == r) cout << max(0ll, tl - tr) << '\n';
        if(l < r) cout << passThrough(tQuery(l, r - 1, 0), tl - l, tr - r) << '\n';
        if(l > r) cout << passThrough(tQuery(n - 1 - (l - 1), n - 1 - r, 1), tl - (n - 1 - (l - 1)), tr - (n - 1 - r)) << '\n';
    }
}

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