Submission #865875

#	Time	Username	Problem	Language	Result	Execution time	Memory
865875		LittleOrange	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	711 ms	156792 KiB

timeleap

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll l0,r0,l1,r1,c,m0,m1;
    obj(ll a,ll b, ll c, ll d, ll e, ll f, ll g):l0(a),r0(b),l1(c),r1(d),c(e),m0(f),m1(g){}
    obj(ll l, ll r):l0(l),r0(r-1),l1(l+1),r1(r),c(0),m0(l),m1(r-1){}
    obj():l0(0),r0(0),l1(0),r1(0),c(0),m0(0),m1(0){}
    ll cal(ll a, ll b) const{
        ll ans = 0;
        a = max(a,l0);
        if (a>r0){
            ans += a-r0;
            a = r0;
        }
        if (l1==r1){
            if (a<=m0) ans += c;
            else ans += c + a-m0;
            if (b<l1) ans += l1-b;
        }else{
            if (a>=m1) ans += a-m1;
            ll ot = max(min(a,m1),m0)-m0+l1;
            if (b<ot) ans += ot-b;
        }
        return ans;
    }
    obj operator+(const obj &o) const{
        if (l1==r1){
            if (o.l1==o.r1){
                return obj(l0,r0,o.l1,o.r1,c+o.cal(l1+0,o.l1),m0,m1);
            }else{
                ll ot = max(min(l1+0,o.m1),o.m0)-o.m0+o.l1;
                return obj(l0,r0,ot,ot,c+o.cal(l1+0,ot),m0,m1);
            }
        }else{
            if (o.l1==o.r1){
                if (o.m0<l1+0){
                    return obj(l0,r0,o.l1,o.r1,o.c+(l1+0-o.m0),m0,m1);
                }else if (o.m0<=r1+0){
                    ll ot = o.m0-0+m0-l1;
                    return obj(l0,r0,o.l1,o.r1,o.c,ot,m1);
                }else{
                    return obj(l0,r0,o.l1,o.r1,o.c,m1,m1);
                }
            }else{
                if (r1+0<=o.m0){
                    return obj(l0,r0,o.l1,o.l1,0,m1,m1);
                }else if (l1+0>=o.m1){
                    return obj(l0,r0,o.r1,o.r1,l1+0-o.m1,m0,m1);
                }else{
                    ll L1,R1,M0,M1;
                    if (l1+0<=o.m0){
                        L1 = o.l1;
                        M0 = m0+o.m0-(l1+0);
                    }else{
                        L1 = l1+0-o.m0+o.l1;
                        M0 = m0;
                    }
                    if (r1+0>=o.m1){
                        R1 = o.r1;
                        M1 = m1-(r1+0-o.m1);
                    }else{
                        R1 = o.r1-(o.m1-(r1+0));
                        M1 = m1;
                    }
                    return obj(l0,r0,L1,R1,0,M0,M1);
                }
            }
        }
    }
    void out()const{
        cout << l0 << " " << r0 << " " << l1 << " " << r1 << " " << c << " " << m0 << " " << m1 << "\n";
    }
};
struct segtree{
    vector<obj> a;
    ll n;
    segtree(ll N):n(N),a(N<<2){}
    void set(ll i, ll l, ll r, ll x, obj o){
        if (l == r) a[i] = o;
        else{
            ll m = l+r>>1;
            if(x<=m) set(i<<1,l,m,x,o);
            else set(i<<1|1,m+1,r,x,o);
            a[i] = a[i<<1]+a[i<<1|1];
        }
    }
    obj query(ll i, ll l, ll r, ll ql, ll qr){
        if (ql<=l&&r<=qr) return a[i];
        else{
            ll m = l+r>>1;
            if (ql<=m&&m<qr) return query(i<<1,l,m,ql,qr)+query(i<<1|1,m+1,r,ql,qr);
            else if (ql<=m )return query(i<<1,l,m,ql,qr);
            else return query(i<<1|1,m+1,r,ql,qr);
        }
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,q;
    cin >> n >> q;
    vector<ll> L(n-1),R(n-1);
    for(ll i = 0;i<n-1;i++) cin >> L[i] >> R[i];
    segtree t0(n-1),t1(n-1);
    for(ll i = 0;i<n-1;i++){
        t0.set(1,0,n-1,i,obj(L[i],R[i]));
        t1.set(1,0,n-1,n-2-i,obj(L[i],R[i]));
    }
    while(q--){
        ll t,a,b,c,d;
        cin >> t >> a >> b >> c;a--;
        if (t==1){
            L[a] = b;
            R[a] = c;
            t0.set(1,0,n-1,a,obj(b,c));
            t1.set(1,0,n-1,n-2-a,obj(b,c));
        }else{
            c--;
            cin >> d;
            ll ans = 0;
            ll t = b;
            ll cur = a;
            if (c>a){
                obj o = t0.query(1,0,n-1,a,c-1);
                //o.out();
                ans = o.cal(b,d);
            }else if (c<a){
                obj o = t1.query(1,0,n-1,(n-2)-(a-1),(n-2)-c);
                //o.out();
                ans = o.cal(b,d);
            }else{
                ans = max(0ll,b-d);
            }
            cout << ans << "\n";
        }
    }
}

Compilation message (stderr)

timeleap.cpp: In constructor 'segtree::segtree(ll)':
timeleap.cpp:77:8: warning: 'segtree::n' will be initialized after [-Wreorder]
   77 |     ll n;
      |        ^
timeleap.cpp:76:17: warning:   'std::vector<obj> segtree::a' [-Wreorder]
   76 |     vector<obj> a;
      |                 ^
timeleap.cpp:78:5: warning:   when initialized here [-Wreorder]
   78 |     segtree(ll N):n(N),a(N<<2){}
      |     ^~~~~~~
timeleap.cpp: In member function 'void segtree::set(ll, ll, ll, ll, obj)':
timeleap.cpp:82:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |             ll m = l+r>>1;
      |                    ~^~
timeleap.cpp: In member function 'obj segtree::query(ll, ll, ll, ll, ll)':
timeleap.cpp:91:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |             ll m = l+r>>1;
      |                    ~^~
timeleap.cpp: In function 'int main()':
timeleap.cpp:121:16: warning: unused variable 't' [-Wunused-variable]
  121 |             ll t = b;
      |                ^
timeleap.cpp:122:16: warning: unused variable 'cur' [-Wunused-variable]
  122 |             ll cur = a;
      |                ^~~

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