제출 #1171076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171076		inkvizytor	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	388 ms	70180 KiB

timeleap

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

#define ll long long

struct vert {
    bool st=0;
    ll a;
    ll b;
    ll c=0;
};

vert sum(vert a, vert b) {
    vert c=a;
    if (a.st) {
        if (b.st) {
            c.b = b.b;
            c.c += max((ll)0, a.b-b.a)+b.c;
        }
        else {
            if (a.b < b.a) {
                c.b = b.a;
            }
            else if (a.b > b.b) {
                c.b = b.b;
                c.c += a.b-b.b;
            }
        }
    }
    else {
        if (b.st) {
            c = b;
            if (b.a < a.a) {
                c.a = a.a;
                c.c += (a.a-b.a);
            }
            else if (b.a > a.b) {
                c.a = a.b;
            }
        }
        else {
            if (a.b <= b.a) {
                c.st = 1;
                c.a = a.b;
                c.b = b.a;
            }
            else if (a.a >= b.b) {
                c.st = 1;
                c.a = a.a;
                c.b = b.b;
                c.c = a.a-b.b;
            }
            else {
                c.a = max(a.a, b.a);
                c.b = min(a.b, b.b);
            }
        }
    }
    return c;
}

vector<vert> d1 ((1<<20), {0, 0, (ll)1e9, 0});
vector<vert> d2 ((1<<20), {0, 0, (ll)1e9, 0});

void init(int n) {
    for (int i = 0; i < n-1; i++) {
        int l, r;
        cin >> l >> r;
        d1[i+(1<<19)] = {0, l-i, r-i-1, 0};
        d2[i+(1<<19)] = {0, l+i, r+i-1, 0};
    }
    for (int i = (1<<19)-1; i > 0; i--) {
        d1[i] = sum(d1[i*2], d1[i*2+1]);
        d2[i] = sum(d2[i*2+1], d2[i*2]);
    }
}

void change(int n) {
    int v, l, r;
    cin >> v >> l >> r;
    v--;
    d1[v+(1<<19)] = {0, l-v, r-v-1, 0};
    d2[v+(1<<19)] = {0, l+v, r+v-1, 0};
    v += 1<<19;
    while (v > 1) {
        v/=2;
        d1[v] = sum(d1[v*2], d1[v*2+1]);
        d2[v] = sum(d2[v*2+1], d2[v*2]);
    }
}

vert calc(int v, int p, int k, int a, int b, vector<vert> &d) {
    //cout << p << ' ' << k << '\n';
    if (a <= p && k <= b) {
        //cout << "x\n";
        //cout << d[v].st << ' ' << d[v].a << ' ' << d[v].b << ' ' << d[v].c << '\n';
        //cout << d[v*2].st << ' ' << d[v*2].a << ' ' << d[v*2].b << ' ' << d[v*2].c << '\n';
        //cout << d[v*2+1].st << ' ' << d[v*2+1].a << ' ' << d[v*2+1].b << ' ' << d[v*2+1].c << '\n';
        return d[v];
    }
    if (b < p || k < a) {
        return {0, 0, (ll)1e9, 0};
    }
    return sum(calc(v*2, p, (p+k)/2, a, b, d), calc(v*2+1, (p+k)/2+1, k, a, b, d));
}

vert calc2(int v, int p, int k, int a, int b, vector<vert> &d) {
    //cout << p << ' ' << k << '\n';
    if (a <= p && k <= b) {
        //cout << "x\n";
        //cout << d[v].st << ' ' << d[v].a << ' ' << d[v].b << ' ' << d[v].c << '\n';
        //cout << d[v*2].st << ' ' << d[v*2].a << ' ' << d[v*2].b << ' ' << d[v*2].c << '\n';
        //cout << d[v*2+1].st << ' ' << d[v*2+1].a << ' ' << d[v*2+1].b << ' ' << d[v*2+1].c << '\n';
        return d[v];
    }
    if (b < p || k < a) {
        return {0, 0, (ll)1e9, 0};
    }
    return sum(calc(v*2+1, (p+k)/2+1, k, a, b, d), calc(v*2, p, (p+k)/2, a, b, d));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    init(n);
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            change(n);
        }
        else {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            a--, c--;
            if (a == c) {
                cout << max(0, b-d) << '\n';
            }
            else if (a < c) {
                vert x = sum({1, b-a, b-a, 0}, calc(1, 0, (1<<19)-1, a, c-1, d1));
                cout << x.c+max((ll)0, (x.b+c)-d) << '\n';
            }
            else {
                vert x = sum({1, b+a-1, b+a-1, 0}, calc2(1, 0, (1<<19)-1, c, a-1, d2));
                //cout << x.a << ' ' << x.b << ' ' << x.c << '\n';
                cout << x.c+max((ll)0, (x.b-c)+1-d) << '\n';
            }
        }
    }
}

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