QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#633286#5415. RopewayCSQ#WA 2ms3796kbC++172.1kb2024-10-12 15:00:102024-10-12 15:00:16

Judging History

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

  • [2024-10-12 15:00:16]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3796kb
  • [2024-10-12 15:00:10]
  • 提交

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'