Submission #506109

#	Time	Username	Problem	Language	Result	Execution time	Memory
506109		ryangohca	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	744 ms	91032 KiB

timeleap

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ti3 tuple<int, int, int>
#define ti4 tuple<int, int, int, int>
#define int long long
// lalalalalalala, you flood into me, slowly from over the horizon  ~ Seunghee, The Fifth Season (SSFWL)
using namespace std;
struct dat{
    int lTime, rTime, timeUsed, powers;
    dat(): lTime(0), rTime(0), timeUsed(0), powers(0){}
    dat(int a, int b, int c, int d): lTime(a), rTime(b), timeUsed(c), powers(d){}
    dat operator +(const dat &oth){
        dat ans;
        ans.timeUsed = timeUsed + oth.timeUsed;
        ans.powers = powers + oth.powers;
        int lrch = lTime + timeUsed, rrch = rTime + timeUsed;
        if (max(lrch, oth.lTime) <= min(rrch, oth.rTime)){
            // in some interval on left node, we can reach the right node on time.
            ans.lTime = max(lrch, oth.lTime) - timeUsed;
            ans.rTime = min(rrch, oth.rTime) - timeUsed;
        } else if (oth.lTime > rrch){
            // right node opens too late, need to wait
            // better for interval to start as late as possible, bcos waiting better than using powers
            ans.lTime = rTime;
            ans.rTime = rTime;
            ans.timeUsed += oth.lTime - rrch;
        } else {
            // right node closes too early, need to use powers
            // better for interval to start as early as possible to use less powers
            ans.powers += lrch - oth.rTime;
            ans.timeUsed -= lrch - oth.rTime;
            ans.lTime = ans.rTime = lTime;
        }
        return ans;
    }
};
vector<pii> v;
struct node{
    int s, e, m;
    dat lft, rgt;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2){
        if (s == e){
            lft = dat(v[s].first, v[s].second, 1, 0);
            rgt = dat(v[s].first, v[s].second, 1, 0);
        } else {
            l = new node(s, m);
            r = new node(m+1, e);
            lft = l->lft + r->lft;
            rgt = r->rgt + l->rgt;
        }
    }
    void upd(int idx){
        if (s == e){
            lft = dat(v[s].first, v[s].second, 1, 0);
            rgt = dat(v[s].first, v[s].second, 1, 0);
            return;
        } else if (idx <= m) l->upd(idx);
        else r->upd(idx);
        lft = l->lft + r->lft;
        rgt = r->rgt + l->rgt;
    }
    dat query(int x, int y, bool islft){
        if (s==x && e==y) return (islft?lft:rgt);
        else if (y <= m) return l->query(x, y, islft);
        else if (x > m) return r->query(x, y, islft);
        else {
            if (islft) return l->query(x, m, islft) + r->query(m+1, y, islft);
            else return r->query(m+1, y, islft) + l->query(x, m, islft);
        }
    }
} *root;
main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    v.push_back({69, 420}); // dummy
    for (int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        v.push_back({a, b-1});
    }
    if (n > 1) root = new node(1, n-1);
    while (q--){
        int t; cin >> t;
        if (t == 1){
            int x, a, b; cin >> x >> a >> b;
            v[x] = {a, b-1};
            if (n > 1) root->upd(x);
        } else {
            int st, l, en, r; cin >> st >> l >> en >> r;
            if (st == en){
                if (r < l) cout << l-r << '\n';
                else cout << "0\n";
                continue;
            }
            bool islft = true;
            if (en < st){
                swap(en, st); //swap(l, r);
                islft = false;
            }
            dat ans = root->query(st, en-1, islft);
            int st_time = max(ans.lTime, l);
            //cout << ans.timeUsed << endl;
            if (ans.rTime < l){
                ans.powers += l-ans.rTime;
                st_time = ans.rTime;
            } 
            int end_time = st_time + ans.timeUsed;
            if (r < end_time){
                ans.powers += end_time - r;
            }
            cout << ans.powers << '\n';
        }
    }
}

Compilation message (stderr)

timeleap.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~

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