Submission #1171029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171029		Piokemon	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	3095 ms	9096 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

struct Node{
    pair<ll,ll> range;
    ll jumps=0;
    ll tajm=1;
};

constexpr int base=(1<<19);
constexpr int N = 3e5;
Node tree[2*base+9];
Node merg(Node a,Node b){
    pair<int,int> nowy;
    nowy.first = max(a.range.first,b.range.first-a.tajm);
    nowy.second = min(a.range.second,b.range.second-a.tajm);
    if (nowy.first <= nowy.second){
        Node c; c.range=nowy; c.tajm=a.tajm+b.tajm; c.jumps=a.jumps+b.jumps;
        return c;
    }
    if (a.range.first > b.range.second-a.tajm){
        Node c;
        c.range = {b.range.second-a.tajm,b.range.second-a.tajm};
        c.tajm = a.tajm+b.tajm;
        c.jumps = a.jumps+b.jumps + a.range.first-(b.range.second-a.tajm);
        return c;
    }
    else{
        Node c;
        c.range = {a.range.second,a.range.second};
        c.jumps = a.jumps+b.jumps;
        c.tajm = a.tajm+b.tajm + (b.range.first-a.tajm-a.range.second);
        return c;
    }
}

Node a[N+9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,q,l,r,t,p,k;
    cin >> n >> q;
    for (int x=1;x<n;x++){
        cin >> l >> r;
        a[x].range = {l,r-1};
    }
    while(q--){
        cin >> t;
        if (t==1){
            cin >> p >> l >> r;
            a[p].range={l,r-1};
        }
        else{
            cin >> p >> l >> k >> r;
            Node opcje; opcje.range = {l,l}; opcje.tajm=0;
            if (p>k){p--;k--;}
            for (int x=p;x!=k;){
                opcje = merg(opcje,a[x]);
                if (p<k)x++;
                else x--;
            }
            Node temp; temp.range={r,r}; temp.tajm=0;
            opcje = merg(opcje,temp);
            cout << opcje.jumps << '\n';
        }
    }
}

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