結果
| 問題 |
No.2988 Min-Plus Convolution Query
|
| コンテスト | |
| ユーザー |
 hos.lyric
|
| 提出日時 | 2024-12-13 00:45:36 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,048 ms / 2,000 ms |
| コード長 | 5,862 bytes |
| コンパイル時間 | 1,972 ms |
| コンパイル使用メモリ | 133,508 KB |
| 実行使用メモリ | 119,156 KB |
| 最終ジャッジ日時 | 2024-12-13 00:46:10 |
| 合計ジャッジ時間 | 25,195 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 40 |
ソースコード
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
namespace smawk_impl {
constexpr int MAX_M = 1 << 20;
constexpr int MAX_N = 1 << 20;
int is0[2 * MAX_M], js0[max(2 * MAX_M, MAX_N)];
template <class Cmp> struct Smawk {
const int m, n;
const Cmp cmp;
vector<int> jms;
Smawk(int m_, int n_, Cmp cmp_) : m(m_), n(n_), cmp(cmp_) {
for (int i = 0; i < m; ++i) is0[i] = i;
for (int j = 0; j < n; ++j) js0[j] = j;
jms.assign(m, -1);
rec(is0, m, js0, n);
}
void rec(int *is, int isLen, int *js, int jsLen) {
if (!isLen || !jsLen) return;
if (isLen < jsLen) {
int len = 0;
for (int y = 0; y < jsLen; ++y) {
const int j = js[y];
for (; len && cmp(is[len - 1], js[len - 1], j); --len) {}
if (len != isLen) js[len++] = j;
}
jsLen = len;
}
int *iis = is + isLen, *jjs = js + jsLen;
int iisLen = 0;
for (int x = 1; x < isLen; x += 2) iis[iisLen++] = is[x];
for (int y = 0; y < jsLen; ++y) jjs[y] = js[y];
rec(iis, iisLen, jjs, jsLen);
for (int x = 0, y = 0; x < isLen; x += 2) {
const int i = is[x];
const int j1 = (x + 1 < isLen) ? jms[is[x + 1]] : js[jsLen - 1];
for (; ; ) {
const int j = js[y];
if (!~jms[i] || cmp(i, jms[i], j)) jms[i] = j;
if (j == j1) break;
++y;
}
}
}
};
} // smawk_impl
template <class Cmp> vector<int> smawk(int m, int n, Cmp cmp) {
return smawk_impl::Smawk<Cmp>(m, n, cmp).jms;
}
constexpr Int INF = 1001001001001001001LL;
int N, Q;
vector<Int> A, B;
vector<int> P, K;
vector<Int> X;
int segN;
// (i, c): k -> c + B[k-i]
vector<vector<pair<int, Int>>> icss;
vector<Int> ans;
vector<pair<int, int>> rec(int u, int l, int r) {
vector<pair<int, int>> kqs;
if (l + 1 == r) {
const int q = l;
if (q < Q) {
kqs.emplace_back(K[q], q);
}
} else {
const int mid = (l + r) / 2;
const auto resL = rec(u << 1, l, mid);
const auto resR = rec(u << 1 | 1, mid, r);
kqs.resize(resL.size() + resR.size());
merge(resL.begin(), resL.end(), resR.begin(), resR.end(), kqs.begin());
}
auto &ics = icss[u];
sort(ics.begin(), ics.end());
// cerr<<u<<" "<<l<<" "<<r<<" "<<kqs<<" "<<ics<<endl;
if (kqs.size() && ics.size()) {
const auto fs = smawk((int)kqs.size(), (int)ics.size(), [&](int e, int f0, int f1) -> bool {
const int k = kqs[e].first;
const int i0 = ics[f0].first;
const int i1 = ics[f1].first;
const Int c0 = ics[f0].second;
const Int c1 = ics[f1].second;
const int j0 = k - i0;
const int j1 = k - i1;
// if (j0 < 0 || j1 < 0) return true;
// if (N <= j0 || N <= j1) return false;
if (j0 < 0 || j1 < 0) return false;
if (N <= j0 || N <= j1) return true;
return (c0 + B[j0] > c1 + B[j1]);
});
// cerr<<" fs = "<<fs<<endl;
for (int e = 0; e < (int)kqs.size(); ++e) {
const int f = fs[e];
const int k = kqs[e].first;
const int i = ics[f].first;
const Int c = ics[f].second;
const int j = k - i;
if (0 <= j && j < N) {
chmin(ans[kqs[e].second], c + B[j]);
}
}
}
return kqs;
}
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
A.resize(N); for (int i = 0; i < N; ++i) scanf("%lld", &A[i]);
B.resize(N); for (int i = 0; i < N; ++i) scanf("%lld", &B[i]);
P.resize(Q);
K.resize(Q);
X.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%d%lld%d", &P[q], &X[q], &K[q]);
P[q] -= 1;
K[q] -= 2;
}
for (segN = 1; segN < Q; segN <<= 1) {}
icss.assign(segN << 1, {});
vector<vector<pair<int, Int>>> qxss(N);
for (int q = 0; q < Q; ++q) {
qxss[P[q]].emplace_back(q, X[q]);
}
for (int i = 0; i < N; ++i) {
const auto &qxs = qxss[i];
const int len = qxs.size();
for (int j = 0; j <= len; ++j) {
int a = (j - 1 >= 0) ? qxs[j - 1].first : 0;
int b = (j < len) ? qxs[j].first : Q;
const Int c = (j - 1 >= 0) ? qxs[j - 1].second : A[i];
// cerr<<i<<" "<<a<<" "<<b<<" "<<c<<endl;
for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) {
if (a & 1) icss[a++].emplace_back(i, c);
if (b & 1) icss[--b].emplace_back(i, c);
}
}
}
ans.assign(Q, INF);
/*
for (int q = 0; q < Q; ++q) {
for (int a = segN + q; a; a >>= 1) {
for (const auto &ic : icss[a]) {
const int j = K[q] - ic.first;
if (0 <= j && j < N) {
chmin(ans[q], ic.second + B[j]);
}
}
}
}
*/
rec(1, 0, segN);
for (int q = 0; q < Q; ++q) {
printf("%lld\n", ans[q]);
}
}
return 0;
}