Submission #965739

#	Time	Username	Problem	Language	Result	Execution time	Memory
965739		Tuanlinh123	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	2558 ms	283612 KiB

timeleap

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
 
const ll maxn=300005, inf=1e9;
ll l[maxn], r[maxn];
 
namespace SegTree
{
    struct seg
    {
        ll l, r, a, b, c, d;
        seg(){}
        seg(ll l, ll r, ll a, ll b, ll c, ll d): l(l), r(r), a(a), b(b), c(c), d(d){}
        bool operator < (const seg &o) {return l<o.l;}
        bool operator == (const seg &o) {return tie(a, b, c, d)==tie(o.a, o.b, o.c, o.d);}
        bool operator != (const seg &o) {return !((*this)==o);}
        seg operator + (const seg &o)
        {
            seg ans;
            if (a==0 && o.l<=b && b<=o.r) ans.l=l, ans.r=r;
            else if (!a) ans.l=1, ans.r=0;
            else ans.l=max(l, o.l-b), ans.r=min(r, o.r-b);
            ans.a=a*o.a, ans.b=b*o.a+o.b;
            ans.c=c+a*o.c, ans.d=d+o.d+b*o.c;
            return ans;
        }
    };
 
    struct Node
    {
        vector <seg> S;
        Node(){}
        Node(ll L, ll R)
        {
            S.pb({0, L, 0, L+1, 0, 0});
            S.pb({L+1, R-1, 1, 1, 0, 0});
            S.pb({R, inf, 0, R, 1, -R+1});
        }
        Node operator + (const Node &o)
        {
            Node ans;
            vector <seg> s;
            for (seg &i:S) for (const seg &j:o.S)
            {
                seg m=i+j;
                if (m.l<=m.r) s.pb(m);
            }
            sort(s.begin(), s.end());
            seg crr=s[0];
            for (ll i=1; i<sz(s); i++)
            {
                if (s[i]!=crr) ans.S.pb(crr), crr=s[i];
                else crr.r=max(crr.r, s[i].r);
            }
            ans.S.pb(crr);
            return ans;
        }
    };
 
    ll n;
    Node pre[maxn*4], suf[maxn*4];
 
    void build(ll i, ll Start, ll End)
    {
		if (Start>End) return;
        if (Start==End) {pre[i]=suf[i]=Node(l[Start], r[Start]); return;}
        ll mid=(Start+End)/2;
        build(i*2, Start, mid), build(i*2+1, mid+1, End);
        pre[i]=pre[i*2]+pre[i*2+1], suf[i]=suf[i*2+1]+suf[i*2];
    }
    void init(ll sz){n=sz, build(1, 1, n);}
 
    void update(ll i, ll Start, ll End, ll idx)
    {
        if (Start==End) {pre[i]=suf[i]=Node(l[idx], r[idx]); return;}
        ll mid=(Start+End)/2;
        if (mid>=idx) update(i*2, Start, mid, idx);
        else update(i*2+1, mid+1, End, idx);
        pre[i]=pre[i*2]+pre[i*2+1], suf[i]=suf[i*2+1]+suf[i*2];
    }
    void update(ll idx){update(1, 1, n, idx);}
 
    Node query(ll i, ll Start, ll End, ll l, ll r, bool s)
    {
        if (Start>=l && End<=r) return s?suf[i]:pre[i];
        ll mid=(Start+End)/2;
        if (mid<l) return query(i*2+1, mid+1, End, l, r, s);
        if (mid+1>r) return query(i*2, Start, mid, l, r, s);
        return s?query(i*2+1, mid+1, End, l, r, s)+query(i*2, Start, mid, l, r, s)
        :query(i*2, Start, mid, l, r, s)+query(i*2+1, mid+1, End, l, r, s);
    }
 
    ll query(ll a, ll b, ll c, ll d)
    {
        if (a==c) return max(0ll, b-d);
        Node ans;
        if (a>c) ans=query(1, 1, n, c, a-1, true);
        else ans=query(1, 1, n, a, c-1, false);
        for (seg &i:ans.S)
            if (i.l<=b && b<=i.r)
                return (b*i.c+i.d)+max(0ll, b*i.a+i.b-d);
        assert(0); return 0;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, q; cin >> n >> q;
    for (ll i=1; i<n; i++) 
        cin >> l[i] >> r[i];
    SegTree::init(n-1);
    for (ll i=1; i<=q; i++)
    {
        ll t; cin >> t;
        if (t==1) {ll p; cin >> p >> l[p] >> r[p], SegTree::update(p);}
        else {ll a, b, c, d; cin >> a >> b >> c >> d; cout << SegTree::query(a, b, c, d) << "\n";}
    }
}

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