結果

問題 No.3367 Looks like a convolution
コンテスト
ユーザー noya2
提出日時 2025-11-15 20:24:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 954 ms / 2,000 ms
コード長 2,328 bytes
コンパイル時間 3,744 ms
コンパイル使用メモリ 295,576 KB
実行使用メモリ 30,008 KB
最終ジャッジ日時 2025-11-17 20:47:16
合計ジャッジ時間 17,858 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define reb(i,s,n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;
bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    if (a.empty()) return os;
    os << a.front();
    for (auto e : a | views::drop(1)){
        os << ' ' << e;
    }
    return os;
}

void dump(auto ...vs){
    ((cout << vs << ' '), ...) << endl;
}

#include<atcoder/lazysegtree>

struct S {
    ll sum;
    int len;
};
S op(S a, S b){
    S c;
    c.sum = a.sum + b.sum;
    c.len = a.len + b.len;
    return c;
}
S e(){
    return S{0,0};
}
S mapping(ll f, S x){
    x.sum += x.len * f;
    return x;
}
ll composition(ll f, ll g){
    return f + g;
}
ll ident(){
    return 0;
}

void solve(){
    int n; cin >> n;
    vector<ll> a(n), b(n);
    rep(i,0,n) cin >> a[i];
    rep(i,0,n) cin >> b[i];
    using dty = atcoder::lazy_segtree<S,op,e,ll,mapping,composition,ident>;
    dty aseg(vector<S>(n,S{0,1})), bseg(vector<S>(n,S{0,1}));
    stack<int> ast, bst;
    auto push = [&](int i, vector<ll> &ab, dty &seg, stack<int> &st){
        int ir = i;
        ll val = ab[i];
        while (!st.empty() && ab[st.top()] > ab[i]){
            int pos = st.top(); st.pop();
            seg.apply(pos+1,ir,-val);
            ir = pos+1;
            val = ab[pos];
        }
        if (!st.empty()){
            int pos = st.top();
            seg.apply(pos+1,ir,-val);
            seg.apply(pos+1,i+1,ab[i]);
        }
        else {
            seg.apply(0,ir,-val);
            seg.apply(0,i+1,ab[i]);
        }
        st.push(i);
    };
    vector<ll> c(n);
    rep(i,0,n){
        push(i,a,aseg,ast);
        push(i,b,bseg,bst);
        int le = 0, ri = i+2;
        while (ri - le > 1){
            int md = midpoint(le,ri);
            if (aseg.get(md-1).sum < bseg.get(i-md+1).sum){
                le = md;
            }
            else {
                ri = md;
            }
        }
        c[i] = aseg.prod(0,le).sum + bseg.prod(0,i+1-le).sum;
    }
    cout << c << '\n';
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();
}
0