src/test/yuki_3330.cpp

• View this file on GitHub
• Last update: 2026-02-20 08:22:15+09:00
• Problem: https://yukicoder.me/problems/no/3330

Depends on

• src/segtree/segtree.hpp
• src/segtree/segtree2d.hpp
• src/template.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/3330"
#include "../segtree/segtree2d.hpp"

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";
}

#line 1 "src/test/yuki_3330.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3330"
#line 2 "src/template.hpp"
#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 S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/segtree/segtree.hpp"

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(a.size())),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 F> int max_right(int l,F f) const {
        if(l==n) return n;
        l+=n;
        S sm=e();
        do {
            while(~l&1) l>>=1;
            if(!f(op(sm,d[l]))){
                while(l<n){
                    l<<=1;
                    if(f(op(sm,d[l]))) sm=op(sm,d[l++]);
                }
                return l-n;
            }
            sm=op(sm,d[l++]);
        } while((l& -l)!=l);
        return n;
    }
    template<typename F> int min_left(int r,F f) const {
        if(!r) return 0;
        r+=n;
        S sm=e();
        do {
            r--;
            while(r>1 and r&1) r>>=1;
            if(!f(op(d[r],sm))){
                while(r<n){
                    r=(2*r+1);
                    if(f(op(d[r],sm))) sm=op(d[r--],sm);
                }
                return r+1-n;
            }
            sm=op(d[r],sm);
        } while((r& -r)!=r);
        return 0;
    }
};

template<class T> using SegtreeFrom=segtree<typename T::S,T::op,T::e>;
#line 3 "src/segtree/segtree2d.hpp"

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(xp.size());
        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);
    }
};
#line 3 "src/test/yuki_3330.cpp"

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";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	01_sample_01.txt	AC	5 ms	4 MB
g++	01_sample_02.txt	AC	5 ms	4 MB
g++	03_almost_max_random_1.txt	AC	6772 ms	417 MB
g++	03_almost_max_random_2.txt	AC	6678 ms	417 MB
g++	03_almost_max_random_3.txt	AC	6757 ms	416 MB
g++	03_almost_max_random_4.txt	AC	6775 ms	415 MB
g++	03_almost_max_random_5.txt	AC	6778 ms	417 MB
g++	04_max_random_1.txt	AC	5718 ms	417 MB
g++	04_max_random_2.txt	AC	5742 ms	415 MB
g++	04_max_random_3.txt	AC	5702 ms	416 MB
g++	05_multi_point_1.txt	AC	7751 ms	417 MB
g++	05_multi_point_2.txt	AC	8051 ms	417 MB
g++	05_multi_point_3.txt	AC	8274 ms	418 MB
g++	05_one_point_1.txt	AC	7877 ms	416 MB
g++	05_one_point_2.txt	AC	7938 ms	417 MB
g++	05_one_point_3.txt	AC	7903 ms	417 MB
g++	06_multi_2_1.txt	AC	7824 ms	417 MB
g++	06_multi_2_2.txt	AC	8102 ms	415 MB
g++	1_small_n_1.txt	AC	2177 ms	157 MB
g++	1_small_n_2.txt	AC	2908 ms	157 MB
g++	1_small_n_3.txt	AC	2787 ms	157 MB
g++	1_small_n_4.txt	AC	2608 ms	157 MB
g++	1_small_n_5.txt	AC	2816 ms	157 MB

Back to top page