Submission #1267825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267825		sitablechair	Dungeon 3 (JOI21_ho_t5)	C++20	0 / 100	562 ms	15364 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=1e5+3,B=320;

struct Query {
    int s,t,u;
} q[N]; 
struct Node {
    int len,s,t,s1,t1;
    bool hasY;
    ll x,y;
};
int n,m,r[N],f[N];
ll pf[N],a[N],b[N],ans[N];
stack<int> st;
vector<ll> big;
vector<int> suc[N],in[N*10];
vector<pair<int,int>> in1[N*10];
Node invl,d[N];

Node mrg(Node A, Node B) {
    if (A.len==-1 || B.len==-1) return invl;
    if (f[A.t]!=B.s) return invl;
    Node ans;
    ans.len=A.len+B.len;
    ans.s=A.s,ans.t=B.t;
    ans.hasY=A.hasY|B.hasY;
    ans.s1=(A.s1==-1?B.s:A.s1);
    ans.t1=(B.t1==-1?A.t:B.t1);
    ans.x=A.x+B.x;
    ans.y=A.y+B.y;
    if (b[A.t]>=b[B.s]) {
        if (A.len==1 || b[A.t1]>=b[A.t]) ans.x+=b[A.t]*(pf[B.s-1]-pf[A.t-1]);
        else {
            ans.y-=b[A.t];
            ans.x+=b[A.t]*(pf[B.s-1]-pf[A.t1-1]);
        }
        
        // if (A.s==1 && A.t==2 && B.s==3 && B.t==3) debug(b[A.t1],b[A.t],ans.x,ans.y);
    } else {
        ans.hasY=1;
        // if (A.t==1 && B.s==2 && B.t==2) debug(ans.x,ans.y);

        if (A.len==1 || b[A.t1]>=b[A.t]) ans.y+=b[A.t];
        else ans.x+=b[A.t]*(pf[A.t-1]-pf[A.t1-1]);
        if (B.len>1) {
            if (b[B.s]>=b[B.s1]) {
                ans.y-=b[B.s];
                ans.x+=b[B.s]*(pf[B.s1-1]-pf[A.t-1]);
                ans.x-=b[B.s]*(pf[B.s1-1]-pf[B.s-1]);
            } else {
                ans.y-=b[B.s];
                ans.x+=b[B.s]*(pf[B.s-1]-pf[A.t-1]);
            }
        }
    } 
    return ans;
}
void recal(int x) {
    ForD(i,min(n+1,(x+1)*B),x*B+1) {
        d[i].len=1,d[i].s1=-1,d[i].t1=-1,d[i].s=d[i].t=i,d[i].x=d[i].y=0;
        d[i].hasY=0;
    }
    ForD(i,min(n+1,(x+1)*B),x*B+1) {
        if (f[i]>(x+1)*B || f[i]==-1) continue;
        d[i]=mrg(d[i],d[f[i]]);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    invl.len=-1;
    For(i,1,n) {
        cin >> a[i];
        pf[i]=pf[i-1]+a[i];
    }
    For(i,1,n) cin >> b[i];
    fill(r+1,r+n+1,n+1);
    r[n+1]=n+2;
    f[n+1]=-1;
    For(i,1,n) {
        while(sz(st) && b[st.top()]>=b[i]) {
            r[st.top()]=i;
            st.pop();
        }
        st.push(i);
    } 
    suc[n].pb(n+1);
    ForD(i,n-1,1) {
        int cur=i+1;
        while(cur<n+1) {
            // if (i==4) debug(cur,r[i]);
            if (cur>n || r[i]<cur) break;
            suc[i].pb(cur);
            big.pb(pf[cur-1]-pf[i-1]);
            cur=r[cur];
        }
    }   
    For(i,1,m) {
        cin >> q[i].s >> q[i].t >> q[i].u;
        big.pb(q[i].u);
    }
    sort(all(big));
    unq(big);
    For(i,1,n) {
        for(auto el: suc[i]) {
            int comp=(lower_bound(all(big),pf[el-1]-pf[i-1])-big.begin())+1;
            in1[comp].pb({i,el});
        }
    }
    For(i,1,m) {
        int comp=(lower_bound(all(big),q[i].u)-big.begin())+1;
        in[comp].pb(i);
    }
    For(i,1,n) {
        f[i]=-1;
        d[i].len=1,d[i].s1=-1,d[i].t1=-1,d[i].s=d[i].t=i,d[i].x=d[i].y=0;
        d[i].hasY=0;
    }
    For(i,0,(n-1)/B) recal(i);
    For(i,1,sz(big)) {

        for(auto el: in1[i]) {
            f[el.ff]=el.ss;
            // debug(d[2].t);
            recal((el.ff-1)/B);
        }
        for(auto el: in[i]) {
            int s=q[el].s,t=q[el].t;
            Node cur;
            cur.hasY=0;
            cur.s1=cur.t1=-1,
            cur.s=cur.t=s;cur.len=1;cur.x=cur.y=0;
            while(true) {
                if (f[cur.t]==-1) {
                    ans[el]=-1;
                    break;
                }
                Node tmp=mrg(cur,d[f[cur.t]]);
                if (tmp.len==-1 || tmp.t > t || pf[t-1]-pf[tmp.t-1]<=big[i-1]) {
                    while(true) {
                        if (f[cur.t]==-1) {
                            ans[el]=-1;
                            break;
                        }
                        Node sus;
                        sus.s1=sus.t1=-1,
                        sus.s=sus.t=f[cur.t];sus.len=1;sus.x=sus.y=0;
                        sus.hasY=0;
                        sus=mrg(cur,sus);
                        if (sus.len==-1) {
                            ans[el]=-1;
                            break;
                        }
                        cur=sus;
                        // if (cur.t==3) debug(cur.x,cur.y);
                        if (pf[t-1]-pf[cur.t-1]<=big[i-1]) break;
                    }
                    break;
                }
                cur=tmp;
            }
            if (ans[el]==-1 || cur.len==-1) continue;
            while(true) {
                Node tmp=mrg(cur,d[f[cur.t]]);
                if (tmp.t>t || tmp.hasY || tmp.len==-1) {
                    while(true) {
                        if (b[f[cur.t]]>b[cur.t] || f[cur.t]==-1) break;
                        Node sus;
                        sus.s1=sus.t1=-1,
                        sus.s=sus.t=f[cur.t];sus.len=1;sus.x=sus.y=0;
                        sus.hasY=0;
                        sus=mrg(cur,sus);
                        if (sus.t>t) break;
                        cur=sus;
                    }
                    break;
                }
                cur=tmp;
            }
            // For(j,1,n) debug(f[j]);
            if (cur.t==t) {
                ll suc=cur.x+cur.y*big[i-1];
                if (cur.len>1 && b[t]>b[cur.t1]) {
                    suc-=b[cur.t1]*(big[i-1]-pf[t-1]+pf[cur.t1-1]);
                }
                ans[el]=suc;
            } else {
                if (cur.len>1 && b[t]>b[cur.t1]) {
                    ll suc=cur.x+cur.y*big[i-1]+b[cur.t1]*(pf[t-1]-big[i-1]+pf[cur.t1-1]);
                    ans[el]=suc;
                } else {
                    ll suc=cur.x+cur.y*big[i-1]+b[cur.t]*(pf[t-1]-pf[cur.t-1]);
                    ans[el]=suc;
                }
            }
            
        }
    }
    For(i,1,m) cout << ans[i] << endl;
    return 0;
}

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