Submission #1179214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179214		Zbyszek99	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	502 ms	89296 KiB

Main

#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 rand(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;

struct line
{
    ll a = 0,b = 0;
    line operator+(const line& other)
    {
        return {a+other.a,b+other.b};
    }
    ll operator()(ll u)
    {
        return u*a+b;
    }
    bool operator<(const line& other) const
    {
        return a < other.a;
    }
};

struct query
{
    int l,r;
    ll u;
    int ind;
    bool operator<(const query& other) const
    {
        return u < other.u;
    }
};

const int tree_siz = 1024*512-1;

int drzewo_A[tree_siz];

int get_max_A(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return 0;
    if(p1 >= s1 && p2 <= s2)
    {
        return drzewo_A[akt-1];
    }
    return max(get_max_A(akt*2,p1,(p1+p2)/2,s1,s2),get_max_A(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}

void updA(int v)
{
    drzewo_A[v-1] = max(drzewo_A[v*2-1],drzewo_A[v*2]);
    if(v != 1) updA(v/2);
}

void changeA(int ind, int x)
{
    drzewo_A[tree_siz/2+ind] = x;
    updA((tree_siz/2+ind+1)/2);
}

line ltree[tree_siz];

line get_f(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return {0,0};
    if(p1 >= s1 && p2 <= s2) return ltree[akt-1];
    return get_f(akt*2,p1,(p1+p2)/2,s1,s2) + get_f(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}

void updl(int v)
{
    ltree[v-1] = ltree[v*2-1] + ltree[v*2];
    if(v != 1) updl(v/2);
}

void change_f(int ind, line f)
{
    ltree[tree_siz/2+ind] = f;
    updl((tree_siz/2+ind+1)/2);
}

ll A_pref[200'002];
ll cost[200'002];
int prev_[200'002];
int nxt[200'002];
ll L[200'002];
ll R[200'002];
ll query_ans[200'002];
bool was_intersect[200'002];
int query_T[200'002];
int query_S[200'002];
ll query_U[200'002];
int qu_l[200'002];
int qu_r[200'002];

vector<pair<int,pll>> events_pref[200'002];
vector<pair<int,pll>> events_suf[200'002];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,q;
    cin >> n >> q;
    A_pref[0] = 1e9;
    rep2(i,1,n)
    {
        ll a;
        cin >> a;
        A_pref[i] = A_pref[i-1] + a;
        changeA(i,a);
    }
    A_pref[n+1] = A_pref[n];
    rep2(i,1,n) cin >> cost[i];
    stack<int> st;
    for(int i = n; i >= 0; i--)
    {
        while(!st.empty() && cost[st.top()] > cost[i])
        {
            st.pop();
        }
        if(siz(st) == 0)
        {
            nxt[i] = n+1;
        }
        else
        {
            nxt[i] = st.top();
        }
        st.push(i);
    }
    st = {};
    rep2(i,1,n)
    {
        while(!st.empty() && cost[st.top()] >= cost[i])
        {
            st.pop();
        }
        if(siz(st) == 0)
        {
            prev_[i] = 0;
        }
        else
        {
            prev_[i] = st.top();
        }
        st.push(i);
    }
    rep2(i,1,n)
    {
        if(prev_[i] > 0) L[i] = A_pref[i-1] - A_pref[prev_[i]-1];
        else L[i] = 1e18;
        R[i] = A_pref[nxt[i]-1] - A_pref[i-1];
    }
    vector<pair<ll,pair<int,line>>> events;
    rep2(i,1,n)
    {
        if(L[i] < R[i])
        {
            events.pb({0,{i,{cost[i],0}}});
            events.pb({L[i],{i,{0,cost[i] * L[i]}}});
            events.pb({R[i],{i,{-cost[i],cost[i] * (L[i] + R[i])}}});
            events.pb({L[i] + R[i],{i,{0,0}}});
        }
        else if(L[i] > R[i])
        {
            events.pb({0,{i,{cost[i],0}}});
            events.pb({R[i],{i,{0,cost[i] * R[i]}}});
            events.pb({L[i],{i,{-cost[i],cost[i] * (L[i] + R[i])}}});
            events.pb({L[i] + R[i],{i,{0,0}}});
        }
        else
        {
            events.pb({0,{i,{cost[i],0}}});
            events.pb({R[i],{i,{-cost[i],cost[i] * (L[i] + R[i])}}});
            events.pb({L[i] + R[i],{i,{0,0}}});
        }
    }
    vector<query> qu;
    rep(qq,q)
    {
        int s,t;
        ll u;
        cin >> s >> t >> u;
        query_T[qq] = t-1;
        query_S[qq] = s;
        query_U[qq] = u;
        t--;
        if(get_max_A(1,0,tree_siz/2,s,t) > u)
        {
            query_ans[qq] = -1;
            continue;
        }
        int l = s;
        int r = t;
        int u_pref = s;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(A_pref[mid-1] - A_pref[s-1] <= u)
            {
                u_pref = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        l = s;
        r = t;
        int u_suf = t;
        while(l <= r)
        {
            int mid = (l+r)/2;
           // cerr << mid << " " << A_pref[t] - A_pref[mid-1] << " bin\n";
            if(A_pref[t] - A_pref[mid-1] <= u)
            {
                u_suf = mid;
                r = mid-1;
            }
            else
            {
                l = mid+1;
            }
        }
       // cerr << u_pref << " " << u_suf << " pref/suf\n";
        // if(u_pref < u_suf)
        // {
        //     if(u_pref + 1 != u_suf)
        //     {
        //         qu.pb({u_pref+1,u_suf-1,u,qq});
        //     }
        // }
        events_pref[s].pb({qq,{u_pref,u}});
        events_suf[u_suf].pb({qq,{t,u}});
    }
    //pref calc:
    vector<pll> stp;
    for(int i = n; i >= 1; i--)
    {
        while(siz(stp) != 0 && cost[i] < cost[stp.back().ff])
        {
            stp.pop_back();
        }
        if(siz(stp) == 0)
        {
            stp.pb({i,0});
        }
        else
        {
            stp.pb({i,stp.back().ss + cost[i] * (A_pref[stp.back().ff-1] - A_pref[i-1])});
        }
        forall(it,events_pref[i])
        {
            int ind = it.ff;
            ll u = it.ss.ss;
            int l = 0;
            int r = siz(stp)-1;
            int ans = 0;
            while(l <= r)
            {
                int mid = (l+r)/2;
                if(A_pref[stp[mid].ff-1] - A_pref[i-1] <= u && stp[mid].ff <= query_T[ind])
                {
                    ans = mid;
                    r = mid-1;
                }
                else
                {
                    l = mid+1;
                }
            }
            query_ans[ind] += stp.back().ss - stp[ans].ss;
         //   cerr << query_ans[ind] << " " << ans << " " << stp[ans].ff << " L_add\n";
            qu_l[ind] = stp[ans].ff+1;
            int v = stp[ans].ff;
            if(nxt[v] <= query_T[ind] || A_pref[query_T[ind]] - A_pref[v-1] > it.ss.ss)
            {
                query_ans[ind] += cost[v] * min(it.ss.ss,A_pref[nxt[v]-1] - A_pref[v-1]);
            }
            else
            {
                qu_r[ind] = -1;
                was_intersect[ind] = 1;
                query_ans[ind] += cost[v] * min(it.ss.ss,A_pref[query_T[ind]] - A_pref[v-1]);
            }
         //   cerr << query_ans[ind] << " L_add\n";
        }
    }
    //suf calc
    vector<int> stc;
    for(int i = n; i >= 1; i--)
    {
        while(siz(stc) != 0 && nxt[i] >= nxt[stc.back()])
        {
            stc.pop_back();
        }
        stc.pb(i);
        forall(it,events_suf[i])
        {
            if(was_intersect[it.ff]) continue;
            int l = 0;
            int r = siz(stc)-1;
            int ans = 0;
            while(l <= r)
            {
                int mid = (l+r)/2;
                if(nxt[stc[mid]] > query_T[it.ff])
                {
                    ans = mid;
                    l = mid+1;
                }
                else
                {
                    r = mid-1;
                }
            }
            int v = stc[ans];
            qu_r[it.ff] = v-1;
            ll l2 = 0;
            if(prev_[v] >= query_S[it.ff]) l2 = A_pref[v-1] - A_pref[prev_[v]-1];
            else l2 = 1e18;
            ll r2 = 0;
            if(nxt[v] <= query_T[it.ff]) r2 = A_pref[nxt[v]-1] - A_pref[v-1];
            else r2 = A_pref[query_T[it.ff]] - A_pref[v-1];
           // cout << i << " " << l << " " << r << " " << u << " " << ans << " " << max(min(u,r) - max(u-l,0LL),0LL)<< " ans\n";
            query_ans[it.ff] += max(min(it.ss.ss,r2) - max(it.ss.ss-l2,0LL),0LL) * cost[v];
          //  cerr << query_ans[it.ff] << " R_add\n";
        }
    }
    rep(qq,q)
    {
        if(qu_l[qq] <= qu_r[qq])
        {
            qu.pb({qu_l[qq],qu_r[qq],query_U[qq],qq});
         //   cerr << qu_l[qq] << " " << qu_r[qq] << " qq\n";
        }
    }
    sort(all(qu));
    sort(all(events));
    int cur_e = 0;
    forall(it,qu)
    {
        while(cur_e < siz(events) && events[cur_e].ff <= it.u)
        {
            change_f(events[cur_e].ss.ff,events[cur_e].ss.ss);
            cur_e++;
        }
        query_ans[it.ind] += get_f(1,0,tree_siz/2,it.l,it.r)(it.u);
    }
    rep(i,q) cout << query_ans[i] << "\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44