QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#633286 | #5415. Ropeway | CSQ# | WA | 2ms | 3796kb | C++17 | 2.1kb | 2024-10-12 15:00:10 | 2024-10-12 15:00:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i < b;i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x.size())
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MAXN = 5e5+5;
struct RMQ{
vector<vector<ll>> jmp;
RMQ(const vector<ll>&V) : jmp(1,V){
for(int pw = 1,k = 1;pw * 2 <= sz(V);pw *= 2, ++k){
jmp.emplace_back(sz(V) - pw*2+1);
rep(j,0,sz(jmp[k]))
jmp[k][j] = min(jmp[k-1][j],jmp[k-1][j+pw]);
}
}
ll query(int a,int b){
assert(a<b);
int dep = 31 - __builtin_clz(b-a);
return min(jmp[dep][a],jmp[dep][b - (1<<dep)]);
}
};
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vector<ll>a(n+2,0),dp(n+2,0),dp2(n+2,0);
vector<int>s(n+2,0);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
char c;
cin>>c;
s[i] = c-'0';
}
int last = -1e9;
multiset<ll>mn;
mn.insert(0);
for(int i=1;i<=n+1;i++){
if(i-k-1 >= 0)mn.erase(mn.find(dp[i-k-1]));
if(last >= i-k)dp[i] = dp[last] + a[i];
else{
dp[i] = *mn.begin()+a[i];
}
mn.insert(dp[i]);
if(s[i])last = i;
}
last = 1e9;
mn.clear();
mn.insert(0);
for(int i=n;i>=0;i--){
if(i+k+1 <=n+1){
mn.erase(mn.find(dp2[i+k+1]));
}
if(last <= i+k)dp2[i] = dp2[last] + a[i];
else{
dp2[i] = *mn.begin()+a[i];
}
mn.insert(dp2[i]);
if(s[i])last = i;
}
/*
for(int i=0;i<=n+1;i++)cout<<dp[i]<<" ";
cout<<'\n';
for(int i=0;i<=n+1;i++)cout<<dp2[i]<<" ";
cout<<'\n';
*/
RMQ rmq(dp2);
int q;
cin>>q;
while(q--){
int p;
ll v;
cin>>p>>v;
ll tmp = a[p];
a[p] = v;
ll ans = 1e18;
int last = 1e9;
for(int i=p+1;i<=min(p+k,n+1);i++){
ans = min(ans,dp[p] + dp2[i] - tmp + v);
if(s[i]){
last = i;
break;
}
}
if(!s[p]){
for(int i=p-1;i>=max(0,p-k+1);i--){
int r = min(i+k,last);
ans = min(ans,dp[i] + rmq.query(p+1,r+1));
if(s[i])break;
}
}
a[p] = tmp;
cout<<ans<<'\n';
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
3 10 3 5 10 7 100 4 3 12 5 100 1 0001000010 2 2 3 6 15 5 6 1 1 1 1 1 00000 1 3 100 5 6 1 1 1 1 1 00100 1 3 100
output:
206 214 0 100
result:
ok 4 number(s): "206 214 0 100"
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3796kb
input:
500 19 6 285203460 203149294 175739375 211384407 323087820 336418462 114884618 61054702 243946442 19599175 51974474 285317523 222489944 26675167 300331960 1412281 324105264 33722550 169011266 1111111110110100011 18 3 127056246 5 100630226 14 301161052 2 331781882 5 218792226 2 190274295 12 49227476 ...
output:
2472886431 2299111966 2796055445 2650202148 2417273966 2508694561 2285479513 2521569560 2521569560 2240907690 2577284958 2521569560 2766700195 2511807344 2521569560 2438434986 2669077215 2682112324 470735446 470735446 211705888 564509290 715543137 470735446 470735446 18 19 19 19 20 19 54 933765048 8...
result:
wrong answer 33rd numbers differ - expected: '849950346', found: '933765048'