結果

問題 No.3367 Looks like a convolution
コンテスト
ユーザー Naru820
提出日時 2025-11-03 00:40:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,597 ms / 2,000 ms
コード長 2,135 bytes
コンパイル時間 5,470 ms
コンパイル使用メモリ 335,180 KB
実行使用メモリ 28,512 KB
最終ジャッジ日時 2025-11-17 20:43:22
合計ジャッジ時間 27,482 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
#define fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr)
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;
constexpr ll inf = 2e18;
constexpr ll mod = 998244353;

static void judge(bool c) {
    std::cout << (c ? "Yes" : "No") << '\n';
}
using namespace atcoder;
struct S{
    ll val;
    int len;
};
S op (S a, S b){
    return S{(a.val + b.val), a.len + b.len};
}
S e(){
    return S{0,0};
}
S mapping(ll f, S x){
    if(f != inf) x.val = f * x.len;
    return x;
}
ll composition(ll f, ll g){
    if(f == inf) return g;
    return f;
}
ll id(){
    return inf;
}

int n,a[200000],b[200000];
int main(){
    cin >> n;
    // minA[i,k],minB[i,k]を管理する範囲代入範囲和遅延セグ木
    lazy_segtree<S, op, e, ll, mapping, composition,id> sega(vector<S>(n, {inf,1}));
    lazy_segtree<S, op, e, ll, mapping, composition,id> segb(vector<S>(n, {inf,1}));
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    // C_k を順に求める
    for(int k = 0; k < n; k++){
        int l = -1,r = k + 1;
        while(r - l > 1){
            int m = (l + r) / 2;
            if(sega.get(m).val <= a[k]){
                l = m;
            }else{
                r = m;
            }
        }
        sega.apply(r, k+1, a[k]);
        l = -1, r = k + 1;
        while(r - l > 1){
            int m = (l + r) / 2;
            if(segb.get(m).val <= b[k]){
                l = m;
            }else{
                r = m;
            }
        }
        segb.apply(r, k+1, b[k]);
        // a,bの大小が切り替わる点を求める
        l = -1, r = k + 1;
        while(r - l > 1){
            int m = (l + r) / 2;
            if(sega.get(m).val <= segb.get(k - m).val){
                l = m;
            }else{
                r = m;
            }
        }
        //cout << "r = " << r << endl;
        cout << sega.prod(0, r).val + segb.prod(0, k + 1 - r).val << ' ';
    }
}
0