Submission #106052

#	Time	Username	Problem	Language	Result	Execution time	Memory
106052		Alexa2001	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	0 / 100	857 ms	525312 KiB

timeleap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 3e5 + 5, inf = 2e9;

int L[Nmax], R[Nmax], tip[Nmax];
int t1[Nmax], t2[Nmax], node1[Nmax], node2[Nmax], id[Nmax], newL[Nmax], newR[Nmax];

int n, q;
ll ans[Nmax];

namespace prepare
{
    void Swap()
    {
        int i;
        for(i=1; i<=(n-1)/2; ++i) swap(L[n-i], L[i]), swap(R[n-i], R[i]);

        for(i=1; i<=q; ++i)
            if(tip[i] == 1) id[i] = n - id[i];
                else node1[i] = n+1-node1[i], node2[i] = n+1-node2[i];
    }

    void Do()
    {
        int i;

        for(i=1; i<n; ++i) L[i] -= i, R[i] -= i + 1;
        for(i=1; i<=q; ++i)
            if(tip[i] == 1) newL[i] -= id[i], newR[i] -= id[i] + 1;
                else if(node1[i] <= node2[i]) t1[i] -= node1[i], t2[i] -= node2[i];
    }

    void Undo()
    {
        int i;
        for(i=1; i<n; ++i) L[i] += i, R[i] += i + 1;
        for(i=1; i<=q; ++i)
            if(tip[i] == 1) newL[i] += id[i], newR[i] += id[i] + 1;
                else if(node1[i] <= node2[i]) t1[i] += node1[i], t2[i] += node2[i];
    }
}

struct tam
{
    int l, r, to;
    ll cost;

    tam() { l = -2e9; r = 2e9; cost = 0; to = inf; }
    tam(int L, int R)
    {
        l = L; r = R; cost = 0; to = inf;
    }
    tam(int L, int R, ll Cost, int To)
    {
        l = L, r = R; cost = Cost; to = To;
    }
};

int par(int x, int l, int r)
{
    return (x > r ? x - r : 0);
}

int modf(int x, int l, int r)
{
    if(x > r) return r;
    if(x < l) return l;
    return x;
}

tam comb(tam a, tam b)
{
    if(a.to != inf)
    {
        if(b.to != inf)
            return tam(a.l, a.r, a.cost + b.cost + par(a.to, b.l, b.r), b.to);
        else
            return tam(a.l, a.r, a.cost + b.cost + par(a.to, b.l, b.r), modf(a.to, b.l, b.r));
    }
    else
    {
        if(a.l > b.r)
        {
            a.to = a.r = a.l;
            return comb(a, b);
        }
        else if(b.l > a.r)
        {
            a.to = a.l = a.r;
            return comb(a, b);
        }

        b.l = max(a.l, b.l);
        b.r = min(a.r, b.r);
        assert(b.l <= b.r);
        return b;
    }
}

#define mid ((st+dr)>>1)
#define left_son ((node<<1))
#define right_son ((node<<1)|1)


class Segtree
{
    tam a[Nmax<<2];
public:
    void build(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node] = tam(L[st], R[st]);
            return;
        }

        build(left_son, st, mid);
        build(right_son, mid+1, dr);

        a[node] = comb(a[left_son], a[right_son]);
    }

    void update(int node, int st, int dr, int pos, int L, int R)
    {
        if(st == dr)
        {
            a[node] = tam(L, R);
            return;
        }

        if(pos <= mid) update(left_son, st, mid, pos, L, R);
            else update(right_son, mid+1, dr, pos, L, R);

        a[node] = comb(a[left_son], a[right_son]);
    }

    tam query(int node, int st, int dr, int Left, int Right)
    {
        if(dr < Left || Right < st) return tam();
        if(Left <= st && dr <= Right) return a[node];

        return comb(query(left_son, st, mid, Left, Right), query(right_son, mid+1, dr, Left, Right));
    }
} aint;



void solve()
{
    prepare :: Do();

    aint.build(1, 1, n-1);

    int i;
    for(i=1; i<=q; ++i)
    {
        if(tip[i] == 1)
        {
            aint.update(1, 1, n-1, id[i], newL[i], newR[i]);
            continue;
        }

        if(node1[i] > node2[i]) continue;

        tam res = aint.query(1, 1, n-1, node1[i], node2[i] - 1);

        tam start(t1[i], t1[i]);
        tam finish(t2[i], t2[i]);

        res = comb(comb(start, res), finish);

        ans[i] = res.cost;
    }

    prepare :: Undo();
}

int main()
{
 //   freopen("input", "r", stdin);
 //   freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    int i;

    cin >> n >> q;
    for(i=1; i<n; ++i) cin >> L[i] >> R[i];

    for(i=1; i<=q; ++i)
    {
        cin >> tip[i];
        if(tip[i] == 1) cin >> id[i] >> newL[i] >> newR[i];
            else cin >> node1[i] >> t1[i] >> node2[i] >> t2[i];
    }

    solve();

    prepare :: Swap();

    solve();

    for(i=1; i<=q; ++i)
        if(tip[i] == 2) cout << ans[i] << '\n';

    return 0;
}

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