QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#586062#5415. RopewayPonyHexWA 1ms7936kbC++204.1kb2024-09-24 00:43:582024-09-24 00:43:58

Judging History

你现在查看的是最新测评结果

  • [2024-09-24 00:43:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7936kb
  • [2024-09-24 00:43:58]
  • 提交

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'