結果
| 問題 | No.2549 Paint Eggs |
| コンテスト | |
| ユーザー |
 Nzt3
|
| 提出日時 | 2024-01-11 09:28:54 |
| 言語 | C++17(gcc12) (gcc 12.4.0 + boost 1.90.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 2,220 bytes |
| 記録 | |
| コンパイル時間 | 1,740 ms |
| コンパイル使用メモリ | 193,228 KB |
| 最終ジャッジ日時 | 2026-07-03 09:18:09 |
| 合計ジャッジ時間 | 5,909 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:91:31: error: non-type template parameters of class type only available with ‘-std=c++20’ or ‘-std=gnu++20’
91 | Lib::segtree<ll,seg_op,seg_e> seg(M);
| ^
main.cpp:91:31: error: non-type template parameters of class type only available with ‘-std=c++20’ or ‘-std=gnu++20’
main.cpp:93:9: error: request for member ‘set’ in ‘seg’, which is of non-class type ‘int’
93 | seg.set(i,A[i]*K);
| ^~~
main.cpp:96:9: error: request for member ‘set’ in ‘seg’, which is of non-class type ‘int’
96 | seg.set(C[i],seg.get(C[i])-A[C[i]]);
| ^~~
main.cpp:96:22: error: request for member ‘get’ in ‘seg’, which is of non-class type ‘int’
96 | seg.set(C[i],seg.get(C[i])-A[C[i]]);
| ^~~
main.cpp:98:14: error: request for member ‘prod’ in ‘seg’, which is of non-class type ‘int’
98 | ll ans=seg.prod(0,M);
| ^~~~
main.cpp:100:9: error: request for member ‘set’ in ‘seg’, which is of non-class type ‘int’
100 | seg.set(C[i-K],seg.get(C[i-K])+A[C[i-K]]);
| ^~~
main.cpp:100:24: error: request for member ‘get’ in ‘seg’, which is of non-class type ‘int’
100 | seg.set(C[i-K],seg.get(C[i-K])+A[C[i-K]]);
| ^~~
main.cpp:101:9: error: request for member ‘set’ in ‘seg’, which is of non-class type ‘int’
101 | seg.set(C[i],seg.get(C[i])-A[C[i]]);
| ^~~
main.cpp:101:22: error: request for member ‘get’ in ‘seg’, which is of non-class type ‘int’
101 | seg.set(C[i],seg.get(C[i])-A[C[i]]);
| ^~~
main.cpp:102:21: error: request for member ‘prod’ in ‘seg’, which is of non-class type ‘int’
102 | ans=min(ans,seg.prod(0,M));
| ^~~~
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
namespace Lib {
template <class S, auto op, auto e>
struct segtree {
int size, _n;
vector<S> seg;
segtree(int n) {
_n = n;
size = 1;
while (size < n) size <<= 1;
seg = vector<S>(size * 2, e());
}
void set(int p, S val) {
p += size;
seg[p] = val;
while (p /= 2) {
seg[p] = op(seg[p * 2], seg[p * 2 + 1]);
}
}
S prod(int l, int r) {
S retL = e(), retR = e();
for (l += size, r += size; l < r; l /= 2, r /= 2) {
if (l % 2) retL = op(retL, seg[l++]);
if (r % 2) retR = op(seg[--r], retR);
}
return op(retL, retR);
}
S get(int p) { return seg[p + size]; }
template <class F>
int max_right(int L, F f) {
L += size;
S sm = e();
do {
while (L % 2 == 0) L /= 2;
if (!f(op(sm, seg[L]))) {
while (L < size) {
L *= 2;
if (f(op(sm, seg[L]))) {
sm = op(sm, seg[L]);
L++;
}
}
return L - size;
}
sm = op(sm, seg[L]);
L++;
} while ((L & -L) != L);
return _n;
}
template <class F>
int min_left(int R, F f) {
R += size;
S sm = e();
do {
R--;
while (R > 1 && R % 2 == 1) R /= 2;
if (!f(op(seg[R], sm))) {
while (R < size) {
R = R * 2 + 1;
if (f(op(seg[R], sm))) {
sm = op(seg[R], sm);
R--;
}
}
return R + 1 - size;
}
sm = op(seg[R], sm);
} while ((R & -R) != R);
return 0;
}
};
} // namespace Lib
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
ll K;
cin>>N>>M>>K;
vector C(N,0),A(M,0);
for(int &i:C)cin>>i,--i;
for(int &i:A)cin>>i;
auto seg_op=[](ll a,ll b){
return min(a,b);
};
auto seg_e=[](){
return (ll)1e18;
};
Lib::segtree<ll,seg_op,seg_e> seg(M);
for(int i=0;i<M;i++){
seg.set(i,A[i]*K);
}
for(int i=0;i<K;i++){
seg.set(C[i],seg.get(C[i])-A[C[i]]);
}
ll ans=seg.prod(0,M);
for(int i=K;i<N;i++){
seg.set(C[i-K],seg.get(C[i-K])+A[C[i-K]]);
seg.set(C[i],seg.get(C[i])-A[C[i]]);
ans=min(ans,seg.prod(0,M));
}
cout<<ans<<'\n';
}