Submission #1170937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170937		Roupiq	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	4 / 100	3092 ms	17096 KiB

timeleap

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

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define len(x) (long)(x).size()
using pii = pair<long, long>;

template <typename T, typename T2>
ostream &operator<<(ostream &o, const pair<T, T2> &p);
template <typename T>
ostream &operator<<(ostream &o, const vector<T> &v);

template <typename T, typename T2>
ostream &operator<<(ostream &o, const pair<T, T2> &p)
{
    return o << "(" << p.x << "," << p.y << ")";
}

template <typename T>
ostream &operator<<(ostream &o, const vector<T> &t)
{
    o << "[";
    for (long i{}; auto u : t)
        o << (i++ ? "," : "") << u;
    return o << "]";
}

long nxt()
{
    long x;
    cin >> x;
    return x;
}

long n, q;
vector<pii> segments;

long query(long a, long b, long c, long d)
{
    long power_uses = 0;
    long height = b;
    // cout << vector({a, b, c, d}) << "\n";
    vector<pii> path;
    for (long i = a - 1; i >= c; i--)
    {
        path.push_back(segments[i]);
    }
    for (long i = a; i < c; i++)
    {
        path.push_back(segments[i]);
    }
    path.push_back({d, d + 1});
    // cout << path << "\n";

    for (auto [x, y] : path)
    {
        height = max(height, x);
        if(height >= y)
        {
            power_uses += height - y + 1;
            // cout << x << " " << y << " " << height - y + 1 << " obnizanie\n";
            height = y - 1;
        }
        height += 1;
    }

    return power_uses;
}

void update(long p, long s, long e) // update semgent
{
    segments[p] = {s, e};
}

int main()
{
    // ios::sync_with_stdio(0), cin.tie(0);
    n = nxt(), q = nxt();
    segments.push_back({0, 0});
    for (long i = 0; i < n - 1; i++)
        segments.push_back({nxt(), nxt()});

    for (long i = 0; i < q; i++)
    {
        if (nxt() == 1)
        {
            long p = nxt(),
                s = nxt(),
                e = nxt();
            update(p, s, e);
        }
        else
        {
            long a = nxt(),
                b = nxt(),
                c = nxt(),
                d = nxt();
            cout << query(a, b, c, d) << "\n";
        }
    }
}

/*
3 3
0 5
0 5
2 1 3 3 3
1 2 0 1
2 1 3 3 3

5 5
3 5
4 8
2 6
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 4 5 1 5
*/

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