QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#192027 | #7522. Sequence Shift | ucup-team266# | WA | 1ms | 7932kb | C++14 | 1.9kb | 2023-09-30 13:20:32 | 2023-09-30 13:20:33 |
Judging History
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'