Submission #1171104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171104		Piokemon	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	533 ms	51560 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 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 = {a.range.first,a.range.first};
        c.tajm = a.tajm+b.tajm - (a.range.first-(b.range.second-a.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];
Node tree[2][2*base+9];

Node merg2(int t, Node a, Node b){
    if (t==0)return merg(a,b);
    else return merg(b,a);
}

void sed(int t, int x, Node val){
    x+=base-1; // nwm czy -1
    tree[t][x]=val;
    while(x>1){
        x/=2;
        tree[t][x] = merg2(t,tree[t][2*x],tree[t][2*x+1]);
    }
}

Node empt;
Node query(int x, int t, int a, int b, int p, int k){
    if (p>b || a>k)return empt;
    if (p<=a && b<=k)return tree[t][x];
    int mid=(a+b)/2;
    return merg2(t,query(2*x,t,a,mid,p,k),query(2*x+1,t,mid+1,b,p,k));
}

int main(){
    empt.range={-1e15,1e15}; empt.tajm=0; empt.jumps=0;
    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};
        sed(0,x,a[x]); sed(1,x,a[x]);
    }
    while(q--){
        cin >> t;
        if (t==1){
            cin >> p >> l >> r;
            a[p].range={l,r-1};
            sed(0,p,a[p]); sed(1,p,a[p]);
        }
        else{
            cin >> p >> l >> k >> r;
            if (p==k){
                cout << max(0,l-r) << '\n';
                continue;
            }
            int lr = (p>k);
            Node opcje; opcje.range = {l,l}; opcje.tajm=0;
            if (lr){
                swap(p,k);
            }
            k--;
            opcje = merg(opcje,query(1,lr,1,base,p,k));
            Node temp; temp.range={r,r}; temp.tajm=0;
            opcje = merg(opcje,temp);
            cout << opcje.jumps << '\n';
        }
    }
}

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