Submission #1174873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174873		Hamed_Ghaffari	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	451 ms	43688 KiB

Main

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

using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) int(x.size())
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 2e5+5;

int n, m, b[MXN], U[MXN], R[MXN];
ll a[MXN], ans[MXN];
vector<int> cmp;
vector<pii> 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 mx[MXN<<2];
pii mn[MXN<<2];

void build(int l=1, int r=n+1, int id=1) {
    if(r-l == 1) {
        mx[id] = a[l]-a[l-1];
        mn[id] = pii(b[l], l);
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    mx[id] = max(mx[lc], mx[rc]);
    mn[id] = min(mn[lc], mn[rc]);
}
int get_max(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) return mx[id];
    if(e<=mid) return get_max(s, e, l, mid, lc);
    if(s>=mid) return get_max(s, e, mid, r, rc);
    return max(get_max(s, e, l, mid, lc), get_max(s, e, mid, r, rc));
}
pii get_min(int s, int e, int l=1, int r=n+1, int id=1) {
    if(s<=l && r<=e) return mn[id];
    if(e<=mid) return get_min(s, e, l, mid, lc);
    if(s>=mid) return get_min(s, e, mid, r, rc);
    return min(get_min(s, e, l, mid, lc), get_min(s, e, mid, r, rc));
}

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];
    }
    for(int i=1; i<=n; i++) cin >> b[i];
    build();
    for(int i=1, s,t; i<=m; i++) {
        cin >> s >> t >> U[i];
        cmp.pb(U[i]);
        if(U[i]<get_max(s, t)) {
            ans[i] = -1;
        }
        else {
            int pos = get_min(max(long(s),lower_bound(a,a+n+1, a[t-1]-U[i])-a+1), t).second;
            Q[s].pb({i, 1});
            Q[pos].pb({i, -1});
            ans[i] = 1ll*b[pos]*(a[t-1]-a[pos-1]);
        }
    }
    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(auto [j, z] : Q[i])
            ans[j] += get(U[j])*z;
    }
    for(int i=1; i<=m; i++) cout << ans[i] << '\n';
    return 0;
}

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