oj.uz

Submission #965737

# Submission time Handle Problem Language Result Execution time Memory
965737 2024-04-19T06:33:06 Z Tuanlinh123 Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 1754 ms 524288 KB 
#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=1000005, 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) {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);
        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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 189264 KB Output is correct
2 Correct 56 ms 189264 KB Output is correct
3 Correct 57 ms 189416 KB Output is correct
4 Correct 56 ms 189260 KB Output is correct
5 Correct 57 ms 189276 KB Output is correct
6 Correct 56 ms 189420 KB Output is correct
7 Correct 57 ms 189268 KB Output is correct
8 Correct 56 ms 189276 KB Output is correct
9 Correct 56 ms 189264 KB Output is correct
10 Correct 57 ms 189268 KB Output is correct
11 Correct 60 ms 189788 KB Output is correct
12 Correct 60 ms 190036 KB Output is correct
13 Correct 60 ms 189916 KB Output is correct
14 Correct 66 ms 189780 KB Output is correct
15 Correct 61 ms 189988 KB Output is correct
16 Correct 61 ms 190044 KB Output is correct
17 Correct 60 ms 189992 KB Output is correct
18 Correct 60 ms 190028 KB Output is correct
19 Correct 70 ms 190200 KB Output is correct
20 Correct 62 ms 190044 KB Output is correct
21 Correct 60 ms 189780 KB Output is correct
22 Correct 59 ms 189784 KB Output is correct
23 Correct 59 ms 189740 KB Output is correct
24 Correct 63 ms 189988 KB Output is correct
25 Correct 61 ms 189780 KB Output is correct
26 Correct 62 ms 189780 KB Output is correct
27 Correct 60 ms 189780 KB Output is correct
28 Correct 59 ms 190032 KB Output is correct
29 Correct 67 ms 190036 KB Output is correct
30 Correct 61 ms 189780 KB Output is correct
31 Correct 60 ms 190032 KB Output is correct
32 Correct 62 ms 190076 KB Output is correct
33 Correct 61 ms 189876 KB Output is correct
34 Correct 59 ms 190036 KB Output is correct
35 Correct 60 ms 190032 KB Output is correct
36 Correct 60 ms 190032 KB Output is correct
37 Correct 61 ms 190032 KB Output is correct
38 Correct 64 ms 190020 KB Output is correct
39 Correct 62 ms 190032 KB Output is correct
40 Correct 60 ms 190032 KB Output is correct
41 Runtime error 266 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1666 ms 383684 KB Output is correct
2 Correct 1700 ms 372736 KB Output is correct
3 Correct 1602 ms 375384 KB Output is correct
4 Correct 1592 ms 369552 KB Output is correct
5 Correct 1668 ms 383316 KB Output is correct
6 Correct 1629 ms 379832 KB Output is correct
7 Correct 1656 ms 367384 KB Output is correct
8 Correct 1690 ms 374516 KB Output is correct
9 Correct 1599 ms 353684 KB Output is correct
10 Correct 1707 ms 385392 KB Output is correct
11 Correct 1620 ms 383704 KB Output is correct
12 Correct 1742 ms 397480 KB Output is correct
13 Correct 1754 ms 400504 KB Output is correct
14 Runtime error 245 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 189264 KB Output is correct
2 Correct 56 ms 189264 KB Output is correct
3 Correct 57 ms 189416 KB Output is correct
4 Correct 56 ms 189260 KB Output is correct
5 Correct 57 ms 189276 KB Output is correct
6 Correct 56 ms 189420 KB Output is correct
7 Correct 57 ms 189268 KB Output is correct
8 Correct 56 ms 189276 KB Output is correct
9 Correct 56 ms 189264 KB Output is correct
10 Correct 57 ms 189268 KB Output is correct
11 Correct 60 ms 189788 KB Output is correct
12 Correct 60 ms 190036 KB Output is correct
13 Correct 60 ms 189916 KB Output is correct
14 Correct 66 ms 189780 KB Output is correct
15 Correct 61 ms 189988 KB Output is correct
16 Correct 61 ms 190044 KB Output is correct
17 Correct 60 ms 189992 KB Output is correct
18 Correct 60 ms 190028 KB Output is correct
19 Correct 70 ms 190200 KB Output is correct
20 Correct 62 ms 190044 KB Output is correct
21 Correct 60 ms 189780 KB Output is correct
22 Correct 59 ms 189784 KB Output is correct
23 Correct 59 ms 189740 KB Output is correct
24 Correct 63 ms 189988 KB Output is correct
25 Correct 61 ms 189780 KB Output is correct
26 Correct 62 ms 189780 KB Output is correct
27 Correct 60 ms 189780 KB Output is correct
28 Correct 59 ms 190032 KB Output is correct
29 Correct 67 ms 190036 KB Output is correct
30 Correct 61 ms 189780 KB Output is correct
31 Correct 60 ms 190032 KB Output is correct
32 Correct 62 ms 190076 KB Output is correct
33 Correct 61 ms 189876 KB Output is correct
34 Correct 59 ms 190036 KB Output is correct
35 Correct 60 ms 190032 KB Output is correct
36 Correct 60 ms 190032 KB Output is correct
37 Correct 61 ms 190032 KB Output is correct
38 Correct 64 ms 190020 KB Output is correct
39 Correct 62 ms 190032 KB Output is correct
40 Correct 60 ms 190032 KB Output is correct
41 Runtime error 266 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -