Submission #1171323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171323		Zbyszek99	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	444 ms	56320 KiB

timeleap

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int NON = -1e9;

struct node
{
    ll comon_l = 0, comon_r = 0,start_time = -1,end_time = -1;
    ll cost = 0;
    node operator+(const node& other)
    {
        node vert;
        if(comon_l != NON && other.comon_l != NON && min(comon_r,other.comon_r) >= max(comon_l,other.comon_l))
        {
            vert = {max(comon_l,other.comon_l),min(comon_r,other.comon_r),-1,-1,0};
        }
        else
        {
            ll beg_;
            ll end_;
            if(comon_l != NON)
            {
                if(other.comon_l != NON)
                {
                    if(comon_l < other.comon_l)
                    {
                        beg_ = comon_r;
                        end_ = other.comon_l;
                    }
                    else
                    {
                        beg_ = comon_l;
                        end_ = other.comon_r;
                    }
                }
                else
                {
                    end_ = other.start_time;
                    if(other.start_time < comon_l)
                    {
                        beg_ = comon_l;
                    }
                    else if(other.start_time > comon_r)
                    {
                        beg_ = comon_r;
                    }
                    else
                    {
                        beg_ = other.start_time;
                    }
                }
            }
            else
            {
                if(other.comon_l != NON)
                {
                    beg_ = end_time;
                    if(end_time < other.comon_l)
                    {
                        end_ = other.comon_l;
                    }
                    else if(end_time > other.comon_r)
                    {
                        end_ = other.comon_r;
                    }
                    else
                    {
                        end_ = end_time;
                    }
                }
                else
                {
                    beg_ = end_time;
                    end_ = other.start_time;
                }
            }
            ll t_start = start_time;
            ll t_end = other.end_time;
            if(comon_l != NON)
            {
                t_start = beg_;
            }
            if(other.comon_l != NON)
            {
                t_end = end_;
            }
            vert = {NON,NON,t_start,t_end,cost + other.cost + max(0LL,beg_-end_)};
        }
        return vert;
    }
};

const int tree_siz = 1024*1024-1;

struct seg_tree
{
    node drzewo[tree_siz-1];
    void upd(int v)
    {  
        drzewo[v-1] = drzewo[v*2-1] + drzewo[v*2]; 
       // cout << drzewo[v-1].comon_l << " " << drzewo[v-1].comon_r << " " << drzewo[v-1].start_time << " " << drzewo[v-1].end_time << " " << drzewo[v-1].cost << " upd\n";
        if(v != 1) upd(v/2);
    }
    void change(int ind, pii seg)
    {
        drzewo[tree_siz/2+ind] = {seg.ff,seg.ss,-1,-1,0};
      //  cout << ind << " " << seg.ff << " " << seg.ss << " change\n";
        upd((tree_siz/2+ind+1)/2);
    }
    void bulid_tree(vector<pii> arr)
    {
        int n = siz(arr);
        rep2(i,1,n-1)
        {
            arr[i].ff -= i;
            arr[i].ss -= i;
        }
        rep(i,n)
        {
      //      cout << arr[i].ff << " " << arr[i].ss << " \n";
            change(i,arr[i]);
        }
      //  cout << " build\n";
    }
    node get_ans(int akt, int p1, int p2, int s1, int s2)
    {
        if(p2 < s1 || p1 > s2) 
        {
            node n = {(int)-1e7,(int)1e9,-1,-1,0};
            return n;
        }
        if(p1 >= s1 && p2 <= s2) 
        {
           // node res = drzewo[akt-1];
       //     cout << drzewo[akt-1].comon_l << " " << drzewo[akt-1].comon_r << " " << drzewo[akt-1].start_time << " " << drzewo[akt-1].end_time << " " << drzewo[akt-1].cost << " p: " << p1 << " " << p2 << " query\n";
            return drzewo[akt-1];
        }
      //  node res = get_ans(akt*2,p1,(p1+p2)/2,s1,s2) + get_ans(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
      //  cout << res.comon_l << " " << res.comon_r << " " << res.start_time << " " << res.end_time << " " << res.cost << " p: " << p1 << " " << p2 << " query\n";
        return get_ans(akt*2,p1,(p1+p2)/2,s1,s2) + get_ans(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
    }
};

ll ans_node(node n1, ll tl, ll tr)
{
    if(n1.comon_l != NON)
    {
        if(tl < n1.comon_l)
        {
            return (ll)(max(0LL,n1.comon_l - tr));
        }
        else if(tl > n1.comon_r)
        {
            return (ll)(tl - n1.comon_r + max(0LL,n1.comon_r - tr));
        }
        else
        {
            return max(0LL,tl-tr);
        }
    }
    else
    {
        return max(0LL,tl-n1.start_time) + max(0LL,n1.end_time - tr) + n1.cost;
    }
}

seg_tree tree1;
seg_tree tree2;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,q;
    cin >> n >> q;
    vector<pii> segs;
    // node node1 = {5,9,-1,-1,0};
    // node node2 = {1,4,-1,-1,0};
    // node union_node = node1 + node2;
    // node node3 = {2,5,-1,-1,0};
    // node node4 = {0,1,-1,-1,0};
    // node union_node2 = node3 + node4;
    // node union_node3 = union_node + union_node2;
    // cout << union_node.comon_l << " " << union_node.comon_r << " " << union_node.start_time << " " << union_node.end_time << " " << union_node.cost << " union\n";
    // cout << union_node2.comon_l << " " << union_node2.comon_r << " " << union_node2.start_time << " " << union_node2.end_time << " " << union_node2.cost << " union2\n";
    // cout << union_node3.comon_l << " " << union_node3.comon_r << " " << union_node3.start_time << " " << union_node3.end_time << " " << union_node3.cost << " union2\n";
    rep(i,n-1)
    {
        int l,r;
        cin >> l >> r;
        segs.pb({l,r-1});
    }
    tree1.bulid_tree(segs);
    reverse(all(segs));
    tree2.bulid_tree(segs);
    reverse(all(segs));
    rep(i,q)
    {
        int t;
        cin >> t;
        if(t == 1)
        {
            int poz,new_l,new_r;
            cin >> poz >> new_l >> new_r;
            poz--;
            tree1.change(poz,{new_l-poz,new_r-poz-1});
            tree2.change((n-2)-poz,{new_l - ((n-2)-poz),new_r - ((n-2)-poz)-1});
        }
        else
        {
            ll tl,tr;
            int l,r;
            cin >> l >> tl >> r >> tr;
            l--;
            r--;
            if(l <= r)
            {
                if(l == r)
                {
                    cout << max(0LL,tl-tr) << "\n";
                    continue;
                }
                r--;
                node n1 = tree1.get_ans(1,0,tree_siz/2,l,r);
              //  cout << n1.comon_l << " " << n1.comon_r << " " << n1.start_time << " " << n1.end_time << " " << n1.cost << " " << tl-l << " " << tr - r - 1<< " node\n";
                cout << ans_node(n1,tl-l,tr - r-1) << "\n";
            }
            else
            {
                l = (n-1)-l;
                r = (n-1)-r;
                if(l == r)
                {
                    cout << max(0LL,tl-tr) << "\n";
                    continue;
                }
                r--;
               // node xd = {(int)-1e7,(int)1e9,-1,-1,0};
                node n1 = tree2.get_ans(1,0,tree_siz/2,l,r);
                //node n2 = (tree2.get_ans(1,0,tree_siz/2,0,1) + tree2.get_ans(1,0,tree_siz/2,2,3)) + xd;
                
              //  cout << l << " " << r << " lr\n";
              //  cout << n1.comon_l << " " << n1.comon_r << " " << n1.start_time << " " << n1.end_time << " " << n1.cost << " " << tl-l << " " << tr - r - 1<< " node\n";
                //cout << n2.comon_l << " " << n2.comon_r << " " << n2.start_time << " " << n2.end_time << " " << n2.cost << " " << tl-l << " " << tr - r - 1<< " node2\n";
                cout << ans_node(n1,tl-l,tr - r-1) << "\n";
            }
        }
    }
}

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