結果

問題 No.3367 Looks like a convolution
コンテスト
ユーザー cho435
提出日時 2025-10-30 03:58:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 576 ms / 2,000 ms
コード長 2,055 bytes
コンパイル時間 1,852 ms
コンパイル使用メモリ 205,088 KB
実行使用メモリ 20,080 KB
最終ジャッジ日時 2025-11-17 20:41:07
合計ジャッジ時間 7,047 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

vector<ll> solve(const vector<ll>& a, const vector<ll>& b) {
	int n = a.size();
	assert((int)b.size() == n);
	vector<array<ll, 3>> mna, mnb;
	mna = mnb = {{-1, -1, 0}};
	auto get_sum = [&](int x, const vector<array<ll, 3>>& vp) {
		assert(x >= 0);
		auto itr = lower_bound(vp.begin(), vp.end(), array<ll, 3>{x, -1, -1});
		assert(itr != vp.end());
		assert(itr != vp.begin());
		auto bitr = prev(itr);
		ll res = 0;
		res += (*bitr)[2];
		res += (x - (*bitr)[0]) * (*itr)[1];
		return res;
	};
	auto get_val = [&](int x, const vector<array<ll, 3>>& vp) -> ll {
		assert(x >= 0);
		return (*lower_bound(vp.begin(), vp.end(), array<ll, 3>{x, -1, -1}))[1];
	};
	vector<ll> res(n);
	rep(i, 0, n) {
		while (mna.back()[1] >= a[i]) mna.pop_back();
		while (mnb.back()[1] >= b[i]) mnb.pop_back();
		mna.push_back({i, a[i], mna.back()[2] + (i - mna.back()[0]) * a[i]});
		mnb.push_back({i, b[i], mnb.back()[2] + (i - mnb.back()[0]) * b[i]});
		if (get_val(0, mnb) >= a[i]) {
			res[i] = get_sum(i, mna);
			continue;
		}
		if (get_val(0, mna) >= b[i]) {
			res[i] = get_sum(i, mnb);
			continue;
		}
		auto f = [&](int x) {
			return get_val(x, mna) < get_val(i - x, mnb);
		};
		int up = i;
		int dw = 0;
		assert(f(dw));
		assert(!f(up));
		while (up - dw > 1) {
			int md = (up + dw) / 2;
			if (f(md)) dw = md;
			else up = md;
		}
		res[i] += get_sum(dw, mna);
		res[i] += get_sum(i - up, mnb);
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	vector<ll> a(n), b(n);
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, n) cin >> b[i];
	auto c = solve(a, b);
	rep(i, 0, n) cout << c[i] << " \n"[i == n - 1];
}
0