Submission #1149589

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

timeleap

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct DS{
    int n;
    vector<int> l, r;
    DS(int ns){
        n = ns;
        l.resize(n);
        r.resize(n);
    }
    void upd(int p, int s, int e){
        l[p] = s; r[p] = e;
    }
    ll get(int a, int b, int c, int d){
        ll out = 0;
        for (int i = a; i < c; i++){
            b = max(b, l[i]);
            if (b < r[i]){
                b++;
            }
            else {
                out += (b - r[i] + 1);
                b = r[i];
            }
        }
        if (b > d) out += (b - d);
        return out;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q; cin>>n>>q;
    vector<int> l(n), r(n);
    for (int i = 1; i < n; i++){
        cin>>l[i]>>r[i];
    }
    
    DS T1(n), T2(n);
    for (int i = 1; i < n; i++){
        T1.upd(i, l[i], r[i]);
        T2.upd(n - i, l[i], r[i]);
    }
    
    while (q--){
        int t; cin>>t;
        if (t == 1){
            int p, s, e; cin>>p>>s>>e;
            T1.upd(p, s, e);
            T2.upd(n - p, s, e);
        }
        else {
            int a, b, c, d; cin>>a>>b>>c>>d;
            if (a <= c){
                cout<<T1.get(a, b, c, d)<<"\n";
            }
            else {
                cout<<T2.get(n - a + 1, b, n - c + 1, d)<<"\n";
            }
        }
    }
}

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