제출 #1136861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136861		pan	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	345 ms	45952 KiB

Main

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << "  " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << "  " << #y << " is " << y << "  " << #z << " is " << z << endl;
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

typedef long long ll;
typedef pair<ll, ll> pi;

const ll INF = 1e16;
static const int N = 200015;

// We replicate the same structures from the “correct code.”

// ========== Segment Tree for range-add, point-query ==========
struct seg {
    // We store data in a 1D array tree[2*N].
    // query(i): returns the sum from root to leaf i.
    // update(l, r, val): adds val to [l..r].
    ll tree[2*N];

    // Returns the prefix-sum-like query at index i.
    ll query(int i){
        ll res = 0;
        for(i += N; i > 0; i >>= 1){
            res += tree[i];
        }
        return res;
    }
    // Add “x” to all elements in [l..r].
    void update(int l, int r, ll x){
        // 0-based => we store data from N..2N-1 in the leaves
        for(l += N, r += N+1; l < r; l >>= 1, r >>= 1){
            if(l & 1) tree[l++] += x;
            if(r & 1) tree[--r] += x;
        }
    }
};

// ========== Segment Tree for range-max query ==========
struct segmax {
    ll tree[2*N];
    // Returns max in [l..r].
    ll query(int l, int r){
        ll res = -INF;
        for(l += N, r += N+1; l < r; l >>= 1, r >>= 1){
            if(l & 1) res = max(res, tree[l++]);
            if(r & 1) res = max(res, tree[--r]);
        }
        return res;
    }
    // Update position i with value x = max(tree[i], x).
    void update(int i, ll x){
        for(i += N; i > 0; i >>= 1){
            tree[i] = max(tree[i], x);
        }
    }
};

// ========== Segment Tree for range-min query (storing (value, index)) ==========
struct segmin {
    pi tree[2*N];  // (value, index)

    // Returns min in [l..r] by comparing .first
    pi query(int l, int r){
        pi res = mp(INF, INF); 
        for(l += N, r += N+1; l < r; l >>= 1, r >>= 1){
            if(l & 1) {
                if(tree[l].f < res.f) res = tree[l];
                l++;
            }
            if(r & 1) {
                --r;
                if(tree[r].f < res.f) res = tree[r];
            }
        }
        return res;
    }
    // Update position i with x if x is “smaller”
    void update(int i, pi x){
        for(i += N; i > 0; i >>= 1){
            if(x.f < tree[i].f) tree[i] = x;
        }
    }
};

// Query struct (same as correct code)
struct query {
    ll U, id, mul;
};

// Global arrays
ll n, Q;
ll X[N], B[N], Rpos[N];  // Rpos corresponds to R[i] in the correct code
ll ans[N];

// For queries
vector<query> queriesAt[N];

// For discretizing “U”
vector<ll> dis;

// Returns index in “dis” for upper_bound on i
int getidx(ll i){
    return (int)(upper_bound(all(dis), i) - dis.begin());
}

// Our main data structures
seg mAdd, cAdd;
segmax finddie;
segmin getmin;

// ---------------------------- main ----------------------------
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> Q;

    // Input for X[2..n+1]
    for(int i = 2; i <= n+1; i++){
        cin >> X[i];
    }
    // Input for B[1..n]
    for(int i = 1; i <= n; i++){
        cin >> B[i];
    }

    // Initialize
    // Clears the segment trees
    for(int i = 0; i < 2*N; i++){
        mAdd.tree[i] = 0;
        cAdd.tree[i] = 0;
        finddie.tree[i] = -INF;
        getmin.tree[i] = mp(INF, INF);
    }

    // Build segmax for the “gap check” finddie
    // We do finddie.update(i-1, X[i]) for i=2..n+1
    for(int i = 2; i <= n+1; i++){
        finddie.update(i-1, X[i]);
    }

    // Build segmin for B[] so we can query min B in [s..t-1]
    // i in [1..n]
    for(int i = 1; i <= n; i++){
        getmin.update(i, mp(B[i], i));
    }

    // Build prefix sums in X[]
    for(int i = 2; i <= n+1; i++){
        X[i] += X[i - 1];
    }

    // Process queries
    for(int i = 1; i <= Q; i++){
        int s, t, u; 
        cin >> s >> t >> u;

        // If the max gap in [s..t-1] > u => ans[i] = -1
        // Using segmax => finddie.query(s, t-1)
        if(finddie.query(s, t-1) > u) {
            ans[i] = -1;
        }
        else {
            // We'll add to queriesAt[s], queriesAt[somethingElse], etc.
            // queries[s].push_back({u, i, +1});
            queriesAt[s].pb({(ll)u, (ll)i, +1LL});

            // findpos = lower_bound(X+1, X+n+1, X[t] - u) - X;
            int findpos = (int)(lower_bound(X + 1, X + (n + 1), X[t] - u) - X);

            // Query segmin in [max(s, findpos) .. t-1] => get (BMin, indexMin)
            int leftBound = max(s, findpos);
            pi ret = getmin.query(leftBound, t - 1);
            ll tmiddle = ret.s;  // the index with min B
            // queries[tmiddle].push_back({u, i, -1});
            queriesAt[tmiddle].pb({(ll)u, (ll)i, -1LL});

            // ans[i] += (X[t] - X[tmiddle]) * B[tmiddle]
            ans[i] += (X[t] - X[tmiddle]) * B[tmiddle];

            // Also push “u” into dis
            dis.pb(u);
        }
    }

    // Now push INF to dis and do unique
    dis.pb(INF);
    discretize(dis);

    // We proceed with the stack-based logic
    // stack<int> st; B[n+1] = -inf; st.push(n+1);
    // The correct code sets B[n+1] = -INF as sentinel
    B[n+1] = -INF;
    stack<int> st;
    st.push(n+1);

    // We'll sweep from s=n down to 1
    ll maxdis = 0; 
    for(int s = n; s >= 1; s--){
        // Keep track of maximum gap so far (not essential to the final logic,
        // but present in the code)
        maxdis = max(maxdis, X[s+1] - X[s]);

        // while(B[st.top()] >= B[s]) => pop
        while(!st.empty() && B[st.top()] >= B[s]){
            int i = st.top();
            st.pop();

            // Use R[i] => which is Rpos[i] in our code
            // but we have NOT set Rpos[i] yet. We want the same approach as the original:
            // Actually, the original sets R[s] AFTER popping bigger B[] from the stack.

            // So for i, we do:
            //   d1 = get( X[i] - X[s] )
            //   d2 = get( X[R[i]] - X[s] )
            //   mAdd.update(d1+1, d2, -B[i])
            //   cAdd.update(d1+1, d2, (X[i]-X[s])*B[i])
            //   cAdd.update(d2+1, N-1, (X[R[i]]-X[i]) * -B[i])

            ll d1 = getidx(X[i] - X[s]);
            ll d2 = getidx(X[Rpos[i]] - X[s]);

            // update in [d1+1..d2] => -B[i]
            // note that “correct code” is 1-based for segment indexes, so we do the same
            mAdd.update(d1 + 1, d2, -B[i]);
            cAdd.update(d1 + 1, d2, (X[i] - X[s]) * B[i]);
            cAdd.update(d2 + 1, (int)dis.size() - 1, (X[Rpos[i]] - X[i]) * (-B[i]));
        }

        // Now st.top() is the next boundary
        int r = st.top();
        Rpos[s] = r;

        // Then we do the “add the min(X[r] - X[s])” logic
        // D = get( X[r] - X[s] )
        ll D = getidx(X[r] - X[s]);

        // Then update:
        //   mAdd.update(1, D, B[s])
        //   cAdd.update(D+1, end, (X[r]-X[s])*B[s])
        mAdd.update(1, D, B[s]);
        cAdd.update(D+1, (int)dis.size() - 1, (X[r] - X[s]) * B[s]);

        // push s
        st.push(s);

        // Now apply queries that start at s
        for(auto &q : queriesAt[s]){
            ll uVal = q.U, qid = q.id, mulSign = q.mul;
            // get idx for uVal => disc
            ll idxU = getidx(uVal);
            // ans[qid] += mulSign * ( mAdd.query(idxU)*uVal + cAdd.query(idxU) )
            ans[qid] += mulSign * ( mAdd.query(idxU)*uVal + cAdd.query(idxU) );
        }
    }

    // Output final answers
    for(int i = 1; i <= Q; i++){
        cout << ans[i] << endl;
    }
    return 0;
}

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