Submission #1170927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170927		Roupiq	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	3070 ms	8788 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) (int)(x).size()
using pii = pair<int, int>;

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 (int i{}; auto u : t)
        o << (i++ ? "," : "") << u;
    return o << "]";
}

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

int n, q;
vector<pii> segments;
const int BASE = 1 << 19;

int query(int a, int b, int c, int d)
{
    int power_uses = 0;
    int height = b;
    // cout << vector({a, b, c, d}) << "\n";
    vector<pii> path;
    for (int i = a - 1; i >= c; i--)
    {
        path.push_back(segments[i]);
    }
    for (int 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(int p, int s, int 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 (int i = 0; i < n - 1; i++)
        segments.push_back({nxt(), nxt()});

    for (int i = 0; i < q; i++)
    {
        if (nxt() == 1)
        {
            int p = nxt(),
                s = nxt(),
                e = nxt();
            update(p, s, e);
        }
        else
        {
            int 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

*/

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