Submission #1171128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171128		Szymon_Pilipczuk	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	2210 ms	168668 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// type,ans+,ansmx, (tmin,tmax) | t.
vector<ll> comb(vector<ll> a,vector<ll> b)
{
    vector<ll> ans;
    if(a[0] == 0 && b[0] == 0)
    {
        if(a[4] >= b[3] && b[4] >= a[3])
        {
            ans.push_back(0);
            ans.push_back(min(a[4],b[4])*-1);
            ans.push_back(min(a[4],b[4]));
            ans.push_back(max(a[3],b[3]));
            ans.push_back(min(a[4],b[4]));
        }
        else
        {
            if(a[4] < b[3])
            {
                ans.push_back(1);
                ans.push_back(a[1]);
                ans.push_back(a[2]);
                ans.push_back(b[3]);
            }
            else
            {
                ans.push_back(1);
                ans.push_back(a[3]*-1 + a[3] - b[4]);
                ans.push_back(a[3]);
                ans.push_back(b[4]);

            }

        }
    }
    else if(a[0] == 1 && b[0] == 0)
    {
        ans.push_back(1);
        ans.push_back(a[1]+b[1]+max(b[2],a[3]));
        ans.push_back(a[2]);
        ans.push_back(min(max(a[3],b[3]),b[4]));
    }
    else if(a[0] == 0 && b[0] == 1)
    {
        ans.push_back(1);
        ans.push_back(b[1]);
        ans.push_back(min(a[2],b[2]));
        ans.push_back(b[3]);
        if(a[3] > b[3])
        {
            ans[1] += max(a[3],b[2]);
            ans[2] = max(a[3],b[2]);
            ans[1] += b[2];
            ans[1]-=max(a[3],b[2]);
        }
    }
    else
    {
        ans.push_back(1);
        ans.push_back(a[1]+b[1]+max(b[2],a[3]));
        ans.push_back(a[2]);
        ans.push_back(b[3]);
    }
    return ans;
}
const int ize = 20; //20
int n,q;
vector<ll> tr[(1<<ize)];
void add(int p,pair<ll,ll> v)
{
    p+=(1<<(ize-1));
    tr[p] = {0,v.second*-1,v.second,v.first,v.second};
    p/=2;
    while( p > 0)
    {
        tr[p] = comb(tr[p*2],tr[p*2+1]);
        p/=2;
    }
}
pair<ll,ll> check(int l,int r,ll s)
{
    l+=(1<<(ize-1));
    r+=(1<<(ize-1));
    pair<ll,ll> cu = {0,s};
    vector<vector<ll>> lv;
    vector<vector<ll>> rv;
    lv.push_back(tr[l]);
    if(l != r) rv.push_back(tr[r]);
    while(l/2 != r/2)
    {
        if(l%2 == 0) lv.push_back(tr[l+1]);
        if(r%2 == 1) rv.push_back(tr[r-1]);
        l/=2;r/=2;
    }
    reverse(rv.begin(),rv.end());
    for(int i = 0;i<rv.size();i++)
    {
        lv.push_back(rv[i]);
    }
    for(int i = 0;i<lv.size();i++)
    {
        //cout<<cu.second<<"\n";
        cu.first+=lv[i][1];
        cu.first+=max(lv[i][2],cu.second);
        if(lv[i][0] == 0)
        {
            cu.second = max(lv[i][3],cu.second);
            cu.second = min(lv[i][4],cu.second);
        }
        else
        {
            cu.second = lv[i][3];
        }
    }
    return cu;
}
vector<ll> tr2[(1<<ize)];
void add2(int p,pair<ll,ll> v)
{
    p+=(1<<(ize-1));
    tr2[p] = {0,v.second*-1,v.second,v.first,v.second};
    p/=2;
    while( p > 0)
    {
        tr2[p] = comb(tr2[p*2],tr2[p*2+1]);
        p/=2;
    }
}
pair<ll,ll> check2(int l,int r,ll s)
{
    //cout<<s<<"\n";
    l+=(1<<(ize-1));
    r+=(1<<(ize-1));
    pair<ll,ll> cu = {0,s};
    vector<vector<ll>> lv;
    vector<vector<ll>> rv;
    lv.push_back(tr2[l]);
    if(l != r) rv.push_back(tr2[r]);
    while(l/2 != r/2)
    {
        if(l%2 == 0) lv.push_back(tr2[l+1]);
        if(r%2 == 1) rv.push_back(tr2[r-1]);
        l/=2;r/=2;
    }
    reverse(rv.begin(),rv.end());
    for(int i = 0;i<rv.size();i++)
    {
        lv.push_back(rv[i]);
    }
    for(int i = 0;i<lv.size();i++)
    {
        //cout<<cu.second<<"\n";
        cu.first+=lv[i][1];
        cu.first+=max(lv[i][2],cu.second);
        if(lv[i][0] == 0)
        {
            cu.second = max(lv[i][3],cu.second);
            cu.second = min(lv[i][4],cu.second);
        }
        else
        {
            cu.second = lv[i][3];
        }
    }
    return cu;
}
pair<ll,ll> prz[299999];
int main()
{
    cin>>n>>q;
    for(int i = 0;i<(1<<ize);i++)
    {
        tr[i] = {0,-1000000000,1000000000,-1000000000,1000000000};
        tr2[i] = {0,-1000000000,1000000000,-1000000000,1000000000};

    }
    for(int i = 0;i<n-1;i++)
    {
        cin>>prz[i].first>>prz[i].second;
        add(i,{prz[i].first-i,prz[i].second-i-1});
        int j = (n-1)-i-1;
        add2(j,{prz[i].first-j,prz[i].second-j-1});
    }
    /*
    for(int i = 1;i<(1<<ize);i++)
    {
        for(int j = 0;j<tr2[i].size();j++)
        {
            cout<<tr2[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    for(int i = 0;i<q;i++)
    {
        int t;
        cin>>t;
        if(t == 1)
        {
            ll p,s,e;
            cin>>p>>s>>e;
            p--;
            add(p,{s-p,e-p-1});
            int j = (n-1)-p-1;
            add2(j,{s-j,e-j-1});
        }
        else
        {
            ll a,b,c,d;
            cin>>a>>b>>c>>d;

            a--;
            c--;
            if(a < c)
            {

                b-=a;
                d-=c;
                pair<ll,ll> ans = check(a,c-1,b);
                cout<<ans.first + max(0ll,ans.second-d)<<"\n";
            }
            else if(c < a)
            {
                a--;
                a = (n-1)-a-1;
                c = (n-1)-c-1;
                b-=a;
                d-=c+1;
                pair<ll,ll> ans = check2(a,c,b);
                cout<<ans.first + max(0ll,ans.second-d)<<"\n";
            }
            else
            {
                cout<<max(0ll,b-d)<<"\n";
            }
        }
    }
}

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