QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#192027#7522. Sequence Shiftucup-team266#WA 1ms7932kbC++141.9kb2023-09-30 13:20:322023-09-30 13:20:33

Judging History

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

  • [2023-09-30 13:20:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7932kb
  • [2023-09-30 13:20:32]
  • 提交

answer

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int B=4000;
int q,a[2000005],b[2000005],n,m,ans[2000005],lst;
pii c[2000005];
void solve()
{
	cin>>n>>q;
	m=n;
	for(int i=1;i<=n;i++) cin>>a[i],c[i]=mp(a[i],i);
	sort(c+1,c+1+n);
	
	for(int i=1;i<=n;i++) cin>>b[i],ans[0]=max(ans[0],a[i]+b[i]);
	priority_queue <int,vector<int>, greater<int> > qa,qb;
	for(int i=1;i<=n;i++) 
	{
		qa.push(a[i]),qb.push(a[i]);
		if(qa.size()>B) qa.pop();
		if(qb.size()>B) qb.pop();
	}
	for(int i=1;i<=n;i++)
	{
		int lim=qa.top()+qb.top()-b[i];
		int p=lower_bound(c+1,c+1+n,mp(lim,0))-c;
		for(int j=p;j<=n;j++)
		{
			int v=c[j].se;
			if(v<i) ans[i-v]=max(ans[i-v],a[v]+b[i]);
		}
	}
	lst=ans[0];
	cout<<lst<<"\n";
	for(int i=1;i<=q;i++)
	{
		int v;
		cin>>v;
//		v^=lst;
		b[++m]=v;
		qb.push(v);
		if(qb.size()>B) qb.pop();
		int lim=qa.top()+qb.top()-b[m];
		int p=lower_bound(c+1,c+1+n,mp(lim,0))-c;
		for(int j=p;j<=n;j++)
		{
			v=c[j].se;
			if(v<m) ans[m-v]=max(ans[m-v],a[v]+b[m]);
		}
		lst=ans[i];
		cout<<lst<<"\n";
	}
}
signed main()
{
//	freopen("K.in","r",stdin);
//	freopen("K.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7932kb

input:

5 3
1 4 3 2 5
7 5 8 3 2
3
6
4

output:

11
12
11
9

result:

wrong answer 2nd lines differ - expected: '13', found: '12'