Submission #1171379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171379		jerzyk	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	387 ms	38732 KiB

timeleap

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef pair<int, int> pi;
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<19;
pair<int, int> drzl[2][2 * N], drzr[2][2 * N];
ll ans[2][2 * N];

pair<ll, pair<pi, pi>> Upd(pi p1, pi k1, pi p2, pi k2)
{
    pi x, y;
    if(max(k1.st, p2.st) <= min(k1.nd, p2.nd))
    {
        x = make_pair(max(k1.st, p2.st), min(k1.nd, p2.nd));
        y = x;
        if(k2.st == k2.nd)
            y = k2;
        if(p1.st == p1.nd)
            x = p1;
        return make_pair(0LL, make_pair(x, y));
    }
    if(k1.nd < p2.st)
    {
        x = make_pair(k1.nd, k1.nd);
        if(p1.st == p1.nd) x = p1;
        y = make_pair(p2.st, p2.st);
        if(k2.st == k2.nd) y = k2;
        return(make_pair(0LL, make_pair(x, y)));
    }
    x = make_pair(k1.st, k1.st);
    if(p1.st == p1.nd) x = p1;
    y = make_pair(p2.nd, p2.nd);
    if(k2.st == k2.nd) y = k2;
    return(make_pair(k1.st - p2.nd, make_pair(x, y)));
}

void U(int r, int v)
{
    pair<ll, pair<pi, pi>> a = Upd(drzl[r][v * 2], drzr[r][v * 2], drzl[r][v * 2 + 1], drzr[r][v * 2 + 1]);
    ans[r][v] = a.st + ans[r][v * 2] + ans[r][v * 2 + 1];
    drzl[r][v] = a.nd.st; drzr[r][v] = a.nd.nd;
}

void Change(int r, int v, pi a)
{
    a.st -= v; a.nd -= v;
    v += N;
    drzl[r][v] = a; drzr[r][v] = a;
    v /= 2;
    while(v > 0)
    {
        U(r, v);
        v /= 2;
    }
}

ll Query(int r, int a, int b, int s, int e)
{
    //cout << r << " " << "Q: " << a << " " << b << "\n";
    s -= a; e -= (b + 1);
    pair<int, int> cur = make_pair(s, s), c2 = make_pair(e, e);
    vector<int> v, v2;
    ll answ = 0LL;
    a += N - 1; b += N + 1;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0)
            v.pb(a + 1);
        if(b % 2 == 1)
            v2.pb(b - 1);
        a /= 2; b /= 2;
    }
    for(int i = (int)v2.size() - 1; i >= 0; --i) v.pb(v2[i]);

    //cout << "QB: " << cur.st << " " << cur.nd << "\n";
    for(int i = 0; i < (int)v.size(); ++i)
    {
        pair<ll, pair<pi, pi>> x = Upd(cur, cur, drzl[r][v[i]], drzr[r][v[i]]);
        answ += x.st + ans[r][v[i]];
        cur = x.nd.nd;
        //cout << v[i] - N << " " << drzl[r][v[i]].st << " " << drzl[r][v[i]].nd << " " << drzr[r][v[i]].st << " " << drzr[r][v[i]].nd << "\n";
        //cout << "QU: " << cur.st << " " << cur.nd << " | " << answ << "\n";
    }
    pair<ll, pair<pi, pi>> x = Upd(cur, cur, c2, c2);
    //cout << "QE: " << cur.st << " " << cur.nd << "\n";
    //cout << "TE: " << c2.st << " " << c2.nd << "\n";
    answ += x.st;
    return answ;
}

void C(int v, int n, pair<int, int> a)
{
    Change(0, v, a);
    Change(1, n - v + 1, a);
}

void Solve()
{
    int n, q;
    pair<int, int> a;
    cin >> n >> q;
    --n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> a.st >> a.nd;
        --a.nd;
        drzl[0][i + N] = make_pair(a.st - i, a.nd - i);
        drzr[0][i + N] = drzl[0][i + N];
        drzl[1][n - i + 1 + N] = make_pair(a.st - (n - i + 1), a.nd - (n - i + 1));
        drzr[1][n - i + 1 + N] = drzl[1][n - i + 1 + N];
    }
    for(int i = N - 1; i >= 1; --i)
        {U(0, i); U(1, i);}

    int r, x, y, s, e;
    for(int i = 1; i <= q; ++i)
    {
        cin >> r;
        if(r == 1)
        {
            cin >> x >> a.st >> a.nd;
            --a.nd;
            C(x, n, a);
            continue;
        }
        cin >> x >> s >> y >> e;
        //cerr << "XD: " << x << " " << y << "\n";
        ll ans;
        if(x <= y)
            ans = Query(0, x, y - 1, s, e);
        else
            ans = Query(1, n - x + 2, n - y + 1, s, e);
        cout << ans << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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