結果

問題 No.3330 Many Point Chmax Range Sum
ユーザー Myu
提出日時 2025-12-13 01:28:00
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2,245 ms / 3,500 ms
コード長 4,906 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,420 ms
コンパイル使用メモリ 317,144 KB
実行使用メモリ 417,920 KB
最終ジャッジ日時 2025-12-13 01:28:47
合計ジャッジ時間 45,462 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename T>bool chmin(T&a,T b){return b<a?(a=b,1):0;}
template<typename T>bool chmax(T&a,T b){return b>a?(a=b,1):0;}

template<class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    vector<S> d;
    segtree(): segtree(1) {}
    explicit segtree(int n_): segtree(vector<S>(n_, e())) {}
    explicit segtree(const vector<S>& a): n(__bit_ceil(si(a))), d(n * 2, e()) {
        rep(i, si(a)) d[n + i] = a[i];
        for(int i = n; --i;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    void set(int i, S x) {
        for(d[i += n] = x; i >>= 1;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    S get(int i) { return d[i + n]; }
    S prod(int l, int r) {
        S L = e(), R = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) L = op(L, d[l++]);
            if(r & 1) R = op(d[--r], R);
        }
        return op(L, R);
    }
};
template<typename K, class S, S (*op)(S, S), S (*e)()> struct segtree_2d {
    int n;
    vector<segtree<S, op, e>> d;
    vector<K> xs;
    vector<vector<K>> ys;
    vector<pair<K, K>> xp;
    vector<vector<pair<K,K>>> yp;
    segtree_2d() {}
    void add_point(K x, K y) { xp.push_back({x, y});}

    void build() {
        sort(all(xp));
        xp.erase(unique(all(xp)), xp.end());
        n = __bit_ceil(si(xp));
        for(auto [x,y]:xp)xs.push_back(x);
        yp.resize(2 * n);
        ys.resize(2 * n);
        rep(i, si(xp)) {
            yp[n + i] = {make_pair(xp[i].se,xp[i].fi)};
            ys[n + i] = {xp[i].se};
        }
        for(int i = n; --i;) {
            merge(all(yp[i * 2]), all(yp[i * 2 + 1]), back_inserter(yp[i]));
            merge(all(ys[i * 2]), all(ys[i * 2 + 1]), back_inserter(ys[i]));
        }
        d.resize(2 * n);
        for(int i = 1; i < 2 * n; i++) {
            d[i] = segtree<S, op, e>(si(yp[i]));
        }
    }

    void set(K x, K y, S v) {
        auto it = lower_bound(all(xp), make_pair(x, y));
        assert(it != xp.end() && it->fi == x && it->se == y);
        int k = it - xp.begin();
        for(k += n; k; k >>= 1) {
            auto it2 = lower_bound(all(yp[k]), make_pair(y,x));
            assert(it2 != yp[k].end());
            int id = it2 - yp[k].begin();
            d[k].set(id, v);
        }
    }
    S get(K x, K y) {
        auto it = lower_bound(all(xp), make_pair(x, y));
        assert(it != xp.end() && it->fi == x && it->se == y);
        int k = it - xp.begin();
        k += n;
        auto it2 = lower_bound(all(yp[k]), make_pair(y,x));
        assert(it2 != yp[k].end());
        int id = it2 - yp[k].begin();
        return d[k].get(id);
    }
    void apply(K x, K y, S v){
        set(x,y,op(get(x,y),v));
    }

    S range(K lv, K rv, K dv, K uv) {
        if(dv >= uv) return e();
        int l = lower_bound(all(xs), lv) - xs.begin();
        int r = lower_bound(all(xs), rv) - xs.begin();
        S sml = e(), smr = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) {
                int li = lower_bound(all(ys[l]), dv) - ys[l].begin();
                int ri = lower_bound(all(ys[l]), uv) - ys[l].begin();
                sml = op(sml, d[l].prod(li, ri));
                l++;
            }
            if(r & 1) {
                --r;
                int li = lower_bound(all(ys[r]), dv) - ys[r].begin();
                int ri = lower_bound(all(ys[r]), uv) - ys[r].begin();
                smr = op(d[r].prod(li, ri), smr);
            }
        }
        return op(sml, smr);
    }
};

long op(long l, long r){
    return l+r;
}
long e(){
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N,K,Q;
    cin>>N>>K>>Q;
    vector<int> A(N);
    rep(i,N)cin>>A[i];
    vector<int> P(K),X(K);
    rep(i,K)cin>>P[i]>>X[i],P[i]--;
    vector<array<int,5>> q(Q);
    rep(i,Q){
        rep(j,4)cin>>q[i][j],q[i][j]-=(j%2==0);
        q[i][4]=i;
    }
    sort(all(q),greater<>());

    segtree_2d<int,long,op,e> seg;
    rep(i,K) seg.add_point(P[i], i);
    rep(i,N) seg.add_point(i,-1);
    seg.build();
    rep(i,N) seg.set(i,-1,A[i]);
    
    vector<stack<pair<int,int>>> st(N);
    vector<long> ans(Q);
    int j=K;
    for(auto [L,R,D,U,qi]:q){
        while(j>L){
            j--;
            if(A[P[j]]>=X[j]) continue;
            while(st[P[j]].size()&&X[j]>=st[P[j]].top().fi){
                seg.set(P[j], st[P[j]].top().se, 0);
                st[P[j]].pop();
            }
            if(st[P[j]].size()){
                seg.set(P[j], st[P[j]].top().se, st[P[j]].top().fi-X[j]);
            }
            seg.set(P[j], j, X[j]-A[P[j]]);
            st[P[j]].push({X[j],j});
        }
        ans[qi]=seg.range(D,U,-1,R);
    }
    rep(i,Q)cout<<ans[i]<<"\n";
}
0