제출 #1174854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174854		Hamed_Ghaffari	Dungeon 3 (JOI21_ho_t5)	C++20	31 / 100	321 ms	22084 KiB

Main

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) int(x.size())

const int MXN = 2e5+5;

int n, m, b[MXN], U[MXN], R[MXN];
ll a[MXN], ans[MXN];
vector<int> cmp, Q[MXN];
int N;

struct {
    ll fen[MXN];
    inline void updx(int p, ll x) {
        for(++p; p<=N; p+=p&-p) fen[p] += x;
    }
    inline ll getx(int p) {
        ll res=0;
        for(++p; p; p-=p&-p) res += fen[p];
        return res;
    }
} fen1, fen2;

inline void updmax(ll x, ll y, ll z, ll r) { // f[u] += z * max(x, y+u) (pos[u]<r)
    int pos = upper_bound(all(cmp), x-y)-cmp.begin();
    if(pos<r) {
        fen1.updx(0, z*x);
        fen1.updx(pos, -z*x + z*y);
        fen2.updx(pos, z);

        fen1.updx(r, -z*y);
        fen2.updx(r, -z);
    }
    else {
        fen1.updx(0, z*x);
        fen1.updx(r, -z*x);
    }
}
inline void updmin(ll x, ll y, ll z, ll r) { // f[u] += z * min(x, y+u) (pos[u]<r)
    int pos = lower_bound(all(cmp), x-y)-cmp.begin();
    if(pos<r) {
        fen1.updx(0, z*y);
        fen2.updx(0, z);
        fen2.updx(pos, -z);
        fen1.updx(pos, -z*y + z*x);

        fen1.updx(r, -z*x);
    }
    else {
        fen1.updx(0, z*y);
        fen2.updx(0, z);

        fen1.updx(r, -z*y);
        fen2.updx(pos, -z);
    }
}
inline void add_interval(ll a, ll b, ll c, ll z) { // [max(b, a+u), min(c, b+u)]
    int pos = lower_bound(all(cmp), c-a)-cmp.begin();
    updmax(b, a, -z, pos);
    updmin(c, b, z, pos);
}
inline ll get(ll u) { // f[u]
    int pos = lower_bound(all(cmp), u)-cmp.begin();
    return fen1.getx(pos) + fen2.getx(pos)*u;
}

int mxsuf[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        a[i] += a[i-1];
    }
    mxsuf[n] = a[n]-a[n-1];
    for(int i=n-1; i>=1; i--) mxsuf[i] = max(1ll*mxsuf[i+1], a[i]-a[i-1]);
    for(int i=1; i<=n; i++) cin >> b[i];
    for(int i=1, s,t; i<=m; i++) {
        cin >> s >> t >> U[i];
        if(t!=n+1 || mxsuf[s]>U[i]) {
            ans[i] = -1;
        }
        else {
            cmp.pb(U[i]);
            Q[s].pb(i);
        }
    }
    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    N = SZ(cmp);
    for(int i=n; i>=1; i--)
        for(R[i]=i+1; R[i]<=n && b[R[i]]>=b[i]; R[i]=R[R[i]]);
    vector<int> stk;
    for(int i=n; i>=1; i--) {
        add_interval(-1e9, a[i-1], a[R[i]-1], b[i]);
        while(!stk.empty() && b[i]<=b[stk.back()]) {
            add_interval(-1e9, a[stk.back()-1], a[R[stk.back()]-1], -b[stk.back()]);
            add_interval(a[i-1], a[stk.back()-1], a[R[stk.back()]-1], b[stk.back()]);
            stk.pop_back();
        }
        stk.pb(i);
        for(int j : Q[i])
            ans[j] = get(U[j]);
    }
    for(int i=1; i<=m; i++) cout << ans[i] << '\n';
    return 0;
}

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