Submission #414935

#	Time	Username	Problem	Language	Result	Execution time	Memory
414935		Pro_ktmr	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	2643 ms	107476 KiB

timeleap

#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

template<typename T>
struct SegmentTree{
private:
    int N;
    vector<T> node;
    function<T(T, T)> F;
    T E;
public:
    void init(int n, function<T(T, T)> f, T e, T def){
        F = f;
        E = e;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, e);
        for(int i=0; i<n; i++) node[N-1+i] = def;
        for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]);
    }
    T& operator [](int a){
        return node[N-1+a];
    }
    void update(int a, T x){
        a += N-1;
        node[a] = x;
        while(a > 0){
            a = (a-1)>>1;
            node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
        }
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return E;
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

struct Gate{
    bool e = false;
    ll A, B, c, t;
    friend Gate operator*(Gate &l, Gate &r){
        if(l.e) return r;
        if(r.e) return l;
        Gate ret;
        ll ok = l.B+1;
        ll ng = l.A;
        while(ok-ng > 1){
            ll m = (ok+ng) / 2;
            if(l.f(m).first + r.f(l.f(m).second).first >
                l.f(l.A).first + r.f(l.f(l.A).second).first){
                ok = m;
            }
            else{
                ng = m;
            }
        }
        ret.B = ng;

        ok = ret.B+1;
        ng = l.A;
        while(ok-ng > 1){
            ll m = (ok+ng) / 2;
            if(r.f(l.f(m).second).second > r.f(l.f(l.A).second).second){
                ok = m;
            }
            else{
                ng = m;
            }
        }
        ret.A = ng;

        ret.c = l.c + r.f(l.t).first;
        ret.t = r.f(l.t).second;
        return ret;
    }
    pair<ll, ll> f(ll x){
        if(x < A) return { c,t };
        if(x < B) return { c,t+x-A };
        return { c+x-B,t+B-A };
    }
};

int N, Q;
ll L[300000], R[300000];
SegmentTree<Gate> stL, stR;

void print(){
    return;
    int l = 6;
    int r = 18;
    cout << "PRINT 0" << endl;
    cout << stL[0].A << " " << stL[0].B << " " << stL[0].c << " " << stL[0].t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL[0].f(i).first << " " << stL[0].f(i).second << endl;
    }
    cout << "PRINT 1" << endl;
    cout << stL[1].A << " " << stL[1].B << " " << stL[1].c << " " << stL[1].t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL[1].f(i).first << " " << stL[1].f(i).second << endl;
    }
    cout << "PRINT [0,2)" << endl;
    cout << stL.query(0, 2).A << " " << stL.query(0, 2).B << " " << stL.query(0, 2).c << " " << stL.query(0, 2).t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL.query(0, 2).f(i).first << " " << stL.query(0, 2).f(i).second << endl;
    }
    cout << "PRINT 2" << endl;
    cout << stL[2].A << " " << stL[2].B << " " << stL[2].c << " " << stL[2].t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL[2].f(i).first << " " << stL[2].f(i).second << endl;
    }
    cout << "PRINT [0,3)" << endl;
    cout << stL.query(0, 3).A << " " << stL.query(0, 3).B << " " << stL.query(0, 3).c << " " << stL.query(0, 3).t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL.query(0, 3).f(i).first << " " << stL.query(0, 3).f(i).second << endl;
    }
    return;
    cout << "PRINT [2,4)" << endl;
    cout << stL.query(2, 4).A << " " << stL.query(2, 4).B << " " << stL.query(2, 4).c << " " << stL.query(2, 4).t << endl;
    for(int i=6; i>=l; i--){
        cout << i << ": " << stL.query(2, 4).f(i).first << " " << stL.query(2, 4).f(i).second << endl;
    }
}

void update(int i){
    stL.update(i, { false,L[i]-i, R[i]-i-1,0,L[i]-i });
    stR.update(N-2-i, { false,L[i]-(N-2-i), R[i]-(N-2-i)-1,0,L[i]-(N-2-i) });
}

signed main(){
    cin >> N >> Q;
    rep(i, N-1) cin >> L[i] >> R[i];

    stL.init(N-1, [](Gate l, Gate r){ return l*r; }, { true,0,0,0,0 }, { true,0,0,0,0 });
    stR.init(N-1, [](Gate l, Gate r){ return l*r; }, { true,0,0,0,0 }, { true,0,0,0,0 });
    rep(i, N-1){
        update(i);
    }

    print();

    rep(i, Q){
        int t;
        cin >> t;
        if(t == 1){
            int p;
            cin >> p;
            p--;
            cin >> L[p] >> R[p];
            update(p);
            print();
        }
        else{
            ll s, t1, g, t2;
            cin >> s >> t1 >> g >> t2;
            s--; g--;
            if(s < g){
                t1 -= s;
                t2 -= g;
                Gate gate = stL.query(s, g);
                ll c = gate.f(t1).first;
                ll t = gate.f(t1).second;
                c += max(0LL, t-t2);
                cout << c << endl;
            }
            else if(s > g){
                t1 -= N-1-s;
                t2 -= N-1-g;
                Gate gate = stR.query(N-1-s, N-1-g);
                ll c = gate.f(t1).first;
                ll t = gate.f(t1).second;
                c += max(0LL, t-t2);
                cout << c << endl;
            }
            else{
                cout << max(0LL, t1-t2) << endl;
            }
        }
    }
}

/*
5 1
10 18
8 16
4 12
13 15
2 2 17 5 18
*/

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
timeleap.cpp:147:5: note: in expansion of macro 'rep'
  147 |     rep(i, N-1) cin >> L[i] >> R[i];
      |     ^~~
timeleap.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
timeleap.cpp:151:5: note: in expansion of macro 'rep'
  151 |     rep(i, N-1){
      |     ^~~
timeleap.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
timeleap.cpp:157:5: note: in expansion of macro 'rep'
  157 |     rep(i, Q){
      |     ^~~

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