QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#586054 | #5415. Ropeway | PonyHex | WA | 3ms | 7908kb | C++20 | 3.6kb | 2024-09-24 00:29:20 | 2024-09-24 00:29:21 |
Judging History
answer
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define double long double
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
//#define int long long
const int N = 5e5 + 50;
const int M = 5e5 + 5;
const ll maxm = 1e18 + 5;
const ll mod = 998244353;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
//random_shuffle(id + 1, id + n + 1);
ll ksm(ll a, ll b);
ll gcd(ll a, ll b);
ll n, k, Q;
ll a[N];
string str;
ll dp[N] = { 0 };//表示在以第i个位置结尾的最小代价
ll b[N] = { 0 };//翻转求第i个位置选了的ans
void solve()
{
//感觉就是个dp,但是这n,q有点太大了点,
//对于每个q都用n的复杂度跑,感觉会t
//但是之前,我们已经获取了一部分,(在更改的元素之前的序列)
//那部分,我们是可以接着用的,每次我们从那个地方开始,能优化一下
//试试
//怎么还有位置是要必须建,等等还有这种好事
//为1的位置相当于把整个数列进行了划分
//到单点修改导致的决策影响仅能影响到下一个一的位置
//在往后的决策都直接加上前置的决策即可
//写的一坨,思路比较纯实现还不好,单调队列能维护出n的复杂度求
//先改一发试试
//改了发t的,然后我发现了题解的重点,g数组
//我们发现单点修改的时候,
priority_queue < pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > >q;
cin >> n >> k;
for (int i = 1; i <= n; i++)cin >> a[i];
cin >> str; str = "1" + str; str = str + "1"; a[n + 1] = 0; a[0] = 0;
q.push({ 0,0 }); dp[0] = 0;
for (int i = 1; i <= n+1; i++) {
while (q.size() && i - q.top().Y > k)q.pop();
dp[i] = q.top().X + a[i];
if (str[i] == '1') {
while (q.size())q.pop();
}
q.push({ dp[i],i });
}
while (q.size())q.pop();
q.push({ 0,n+1 }); b[n+1] = 0;
for (int i = n; i>=0; i--) {
while (q.size() && q.top().Y - i > k)q.pop();
b[i] = q.top().X + a[i];
if (str[i] == '1') {
while (q.size())q.pop();
}
q.push({ b[i],i });
}
while (q.size())q.pop();
cin >> Q;
for (int i = 1; i <= Q; i++) {
ll pos, val; cin >> pos >> val;
//单点修改以后可怎么搞
//总不能再跑完,试试,要不
if (str[pos] == '1') {
cout << dp[n + 1] + (-a[pos] + val) << endl; continue;
}
//有点想法,其实可以看做两种选择,一种是更新后选,一种不选
//如果选,ans应为dp+b-a
//如果不选呢,大于pos位置的很多元素有选pos的能力
//
ll ans = dp[pos] + b[pos] - a[pos] * 2 + val;
// << ans << endl;
for (int ii = max(0ll, pos - k); ii < pos; ii++) {
if (str[ii] == '1') {
while (q.size())q.pop();
}
q.push({ dp[ii],ii });
}
for (int ii = pos+1; ii <= min(n + 1, pos + k); ii++) {
while (q.size() && ii - q.top().Y > k)q.pop();
ll mid= q.top().X + a[ii];
//cout << q.top().X << " " << q.top().Y << endl;
if (str[ii] == '1') {
while (q.size())q.pop();
}
q.push({ mid,ii });
mid -= a[ii];
//cout << mid << " " << b[ii] << " " << ii << endl;
mid += b[ii];
ans = min(ans, mid);
}
cout << ans << endl;
while (q.size())q.pop();
}
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
/*PonyHex*/
ll ksm(ll a, ll b) {
ll base = a;
ll ans = 1;
while (b) {
if (b & 1)ans *= base % mod;
ans %= mod;
base *= base; base %= mod;
b >>= 1;
}
return ans % mod;
}
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7908kb
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: 3ms
memory: 7716kb
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 849950346 8...
result:
wrong answer 116th numbers differ - expected: '4010332301', found: '3553535288'