結果

問題 No.3367 Looks like a convolution
コンテスト
ユーザー tassei903
提出日時 2025-11-18 17:34:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 955 ms / 2,000 ms
コード長 6,483 bytes
コンパイル時間 3,370 ms
コンパイル使用メモリ 292,252 KB
実行使用メモリ 28,488 KB
最終ジャッジ日時 2025-11-18 17:34:31
合計ジャッジ時間 18,872 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }
 
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
 
#define i128 __int128_t
 
struct _ {
   _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

void debug(auto ...vs) {
    ((cerr << vs << " "), ...) << endl;
}

using U = uint64_t;
template<class S, S (*op)(S, S), S (*e)(), class F, S (*mpp)(F, S), F (*cmpo)(F, F), F (*id)()> struct lazy_segtree {
   lazy_segtree() : lazy_segtree(0) {}
   explicit lazy_segtree(int n) : lazy_segtree(vector<S>(n, e())) {}
   explicit lazy_segtree(const vector<S>& v) : n(sz(v)) {
      s = bit_ceil(U(n));
      log = countr_zero(U(s));
      d = vector<S>(2 * s, e());
      lz = vector<F>(s, id());
      rep(i, n) d[s + i] = v[i];
      per(i, s, 1) update(i);
   }
   void set(int p, S x) {
      p += s;
      PUSH(p);
      d[p] = x;
      rep(i, 1, log + 1) update(p >> i);
   }
   S get(int p) {
      p += s;
      PUSH(p);
      return d[p];
   }
   S prod(int l, int r) {
      if(l == r) return e();
      l += s, r += s;
      per(i, log + 1, 1) {
         if(((l >> i) << i) != l) push(l >> i);
         if(((r >> i) << i) != r) push((r - 1) >> i);
      }
      S sml = e(), smr = e();
      while(l < r) {
         if(l & 1) sml = op(sml, d[l++]);
         if(r & 1) smr = op(d[--r], smr);
         l >>= 1, r >>= 1;
      }
      return op(sml, smr);
   }
   S all_prod() { return d[1]; }
   void apply(int p, F f) {
      // assert(0 <= p && p < n);
      p += s;
      PUSH(p);
      d[p] = mpp(f, d[p]);
      rep(i, 1, log + 1) update(p >> i);
   }
   void apply(int l, int r, F f) {
      // assert(0 <= l && l <= r && r <= _n);
      if(l == r) return;
      l += s, r += s;

      per(i, log + 1, 1) {
         if(((l >> i) << i) != l) push(l >> i);
         if(((r >> i) << i) != r) push((r - 1) >> i);
      }
      int ml = l, mr = r;
      while(l < r) {
         if(l & 1) all_apply(l++, f);
         if(r & 1) all_apply(--r, f);
         l >>= 1, r >>= 1;
      }
      l = ml, r = mr;
      rep(i, 1, log + 1) {
         if(((l >> i) << i) != l) update(l >> i);
         if(((r >> i) << i) != r) update((r - 1) >> i);
      }
   }
   template<class G> int max_right(int l, G g) {
      assert(g(e()));
      if(l == n) return n;
      l += s;
      PUSH(l);
      S sm = e();
      do {
         while(~l & 1) l >>= 1;
         if(!g(op(sm, d[l]))) {
            while(l < s) {
               push(l);
               l <<= 1;
               if(g(op(sm, d[l]))) {
                  sm = op(sm, d[l]);
                  l++;
               }
            }
            return l - s;
         }
         sm = op(sm, d[l]);
         l++;
      } while((l & -l) != l);
      return n;
   }
   template<class G> int min_left(int r, G g) {
      assert(g(e()));
      if(r == 0) return 0;
      r += s;
      PUSH(r - 1);
      S sm = e();
      do {
         r--;
         while(r > 1 && r & 1) r >>= 1;
         if(!g(op(d[r], sm))) {
            while(r < s) {
               push(r);
               r = (2 * r + 1);
               if(g(op(d[r], sm))) {
                  sm = op(d[r], sm);
                  r--;
               }
            }
            return r + 1 - s;
         }
         sm = op(d[r], sm);
      } while((r & -r) != r);
      return 0;
   }
   S operator[](int k) { return get(k); }
   int len() { return n; }

   private:
   int n, s, log;
   vector<S> d;
   vector<F> lz;
   void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
   void all_apply(int k, F f) {
      d[k] = mpp(f, d[k]);
      if(k < s) lz[k] = cmpo(f, lz[k]);
   }
   void push(int k) {
      all_apply(2 * k, lz[k]);
      all_apply(2 * k + 1, lz[k]);
      lz[k] = id();
   }
   void PUSH(int k) { per(i, log + 1, 1) push(k >> i); }
};

struct S {
    ll s;
    int l;
};

S op(S x, S y) {
    return {x.s + y.s, x.l + y.l};
}

S e() {
    return {0, 0};
}

S mapp(ll f, S x) {
    return {f * x.l + x.s, x.l};
}

ll comp(ll f, ll g) {
    return f + g;
}

ll id() {
    return 0;
}

void solve() {
    int n;cin >> n;
    vi a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    stack<int> ska, skb;
    ska.push(-1), skb.push(-1);
    lazy_segtree<S, op, e, ll, mapp, comp, id> lsta(n), lstb(n);
    rep(i, n) lsta.set(i, S{0, 1});
    rep(i, n) lstb.set(i, S{0, 1});
    vl res(n, 0);

    rep(i, n) {
        while (ska.top() != -1 and a[ska.top()] >= a[i]) {
            int x = ska.top();ska.pop();
            lsta.apply(ska.top() + 1, x + 1, -a[x]);
        }
        lsta.apply(ska.top() + 1, i+1, a[i]);
        while (skb.top() != -1 and b[skb.top()] >= b[i]) {
            int x = skb.top();skb.pop();
            lstb.apply(skb.top() + 1, x + 1, -b[x]);
        }
        lstb.apply(skb.top() + 1, i+1, b[i]);
        ska.push(i);
        skb.push(i);

        int ok = i+1, ng = -1;
        // a[j] > b[i-j] 
        // j = 0, ... i
        while (abs(ng - ok) > 1) {
            int mid = (ok + ng) / 2;
            if (lsta.get(mid).s > lstb.get(i - mid).s) {
                ok = mid;
            }
            else {
                ng = mid;
            }
        }
        // debug(i, ok);
        res[i] = lsta.prod(0, ok).s + lstb.prod(0, i + 1 - ok).s;
        
        // rep(i, n) {
        //     cerr << lsta.get(i).s << " ";
        // }
        // cerr << endl;
        // rep(i, n) {
        //     cerr << lstb.get(i).s << " ";
        // }
        // cerr << endl;
        // cerr << endl;
        
    }

    rep(i, n) {
        if (i) cout << " ";
        cout << res[i];
    }
    cout << endl;

}

int main() {

    // int T;cin >> T;
	int T = 1;
    while(T--) {
        solve();
    }
    
}
0