QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#586062 | #5415. Ropeway | PonyHex | WA | 1ms | 7936kb | C++20 | 4.1kb | 2024-09-24 00:43:58 | 2024-09-24 00:43:58 |
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();
/*
reverse(a + 1, a + n + 1);
reverse(str.begin()+1, str.begin() + n + 1);
q.push({ 0,0 }); b[0] = 0;
for (int i = 1; i <= n + 1; i++) {
while (q.size() && i - q.top().Y > 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();
reverse(a + 1, a + n + 1);
reverse(str.begin() + 1, str.begin() + n + 1);
reverse(b, b + n + 2);*/
for (int i = 1; i <= n; i++) b[i] -= a[i];
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+1); 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: 0
Wrong Answer
time: 1ms
memory: 7936kb
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:
108 114 0 100
result:
wrong answer 1st numbers differ - expected: '206', found: '108'