Submission #1171030

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

timeleap

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
#define all(a) a.begin(), a.end()
#define print(a) for (auto elem:a) cout<<elem<<' '; cout<<'\n'
#define segprep(b) resize(1<<((int)ceil(log2(b.size()))+1))
#define FOR(a) for (int _ = 0; _ < a; _++)

int n, q;
vector<pll> times;
ll cost_of_travel(int node, ll time, int goal, ll goal_time){
    ll cost = 0;
    bool forw = node < goal;
    ll d = (forw ? 1 : -1);
    ll d2 = (forw ? 0 : -1);
    for (;(forw ? node < goal : node > goal); node += d){
        if (times.at(node+d2).first <= time && time < times.at(node+d2).second){
            time++;
            continue;
        }
        if (time < times.at(node+d2).first){
            time = times.at(node+d2).first+1;
            continue;
        }
        int diff = time-times.at(node+d2).second+1;
        cost += diff;
        time = times.at(node+d2).second;
    }
    if (time > goal_time){
        cost += time-goal_time;
    }
    return cost;
}

void solve1(){
    int t, a, b, c, d, p, s, e;
    while(q--){
        cin>>t;
        if (t == 1){
            cin>>p>>s>>e;
            times.at(p-1) = {s, e};
            continue;
        }
        cin>>a>>b>>c>>d;
        cout<<cost_of_travel(a-1, b, c-1, d)<<'\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>q;
    times.resize(n-1);
    for (auto &[l, r]:times) cin>>l>>r;
    solve1();
}

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