QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137819 | #6794. Sequence to Sequence | vme50 | WA | 130ms | 5636kb | C++17 | 1.8kb | 2023-08-10 17:58:39 | 2023-08-12 03:46:57 |
Judging History
你现在查看的是最新测评结果
- [2023-08-12 03:46:45]
- hack成功,自动添加数据
- (//qoj.ac/hack/351)
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-08-10 17:58:39]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
const int INF=1e9;
int T,n,o,w1,w2,a[N],b[N],L[N],R[N],q1[N],q2[N];ll ans;
void upd(int x)
{
while(q1[0]<=q1[1] && L[x]>=L[q1[q1[1]]]) --q1[1];
while(q2[0]<=q2[1] && R[x]<=R[q2[q2[1]]]) --q2[1];
q1[++q1[1]]=x;q2[++q2[1]]=x;
}
int lim1() {return q1[0]<=q1[1]?L[q1[q1[0]]]:0;}
int lim2() {return q2[0]<=q2[1]?R[q2[q2[0]]]:INF;}
void slv()
{
scanf("%d",&n);o=w1=w2=L[n+1]=R[n+1]=ans=0;
q1[0]=q2[0]=2;q1[1]=q2[1]=1;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<=n;++i) if(!a[i] && b[i]) {printf("-1\n");return;}
for(int i=1;i<=n;++i) if(b[i]) L[i]=max(a[i]-b[i],0),R[i]=a[i]-1;
else L[i]=a[i],R[i]=INF;
for(int i=1,w,t=1,t1,t2;i<=n;++i)
{
while(q1[0]<=q1[1] && q1[0]<i) ++q1[0];
while(q2[0]<=q2[1] && q2[0]<i) ++q2[0];
while(t<=n+1 && w1>=L[t] && w1<=R[t]) upd(++t);
if(i==t)
{
if(w1<L[i])
{
t1=L[i];t2=t1-a[i]+b[i];
ans+=abs(w1-t1);w1=t1;if(b[i]) ans+=abs(w2-t2),w2=t2;
}
else
{
t1=R[i];t2=t1-a[i]+b[i];
ans+=abs(w1-t1);w1=t1;if(b[i]) ans+=abs(w2-t2),w2=t2;
}while(t<=n+1 && w1>=L[t] && w1<=R[t]) upd(++t);
}if(!b[i]) continue;w=w2-w1+a[i]-b[i];ans+=abs(w);
if(w1<L[t])
{
w=max(w,0);
while(t<=n+1 && w1<L[t])
{
if(lim2()<L[t]) {w1=min(w1+w,lim2());break;}
if(w1+w<L[t]) {w1+=w;break;}w-=L[t]-w1;w1=L[t];
while(t<=n+1 && w1>=L[t] && w1<=R[t]) upd(++t);
}
}
else
{
w=max(-w,0);
while(t<=n+1 && w1>R[t])
{
if(lim1()>R[t]) {w1=max(w1-w,lim1());break;}
if(w1-w>R[t]) {w1-=w;break;}w-=w1-R[t];w1=R[t];
while(t<=n+1 && w1>=L[t] && w1<=R[t]) upd(++t);
}
}w2=w1-a[i]+b[i];
}ans+=w1+w2;printf("%lld\n",ans/2);
}
int main() {scanf("%d",&T);while(T--) slv();return 0;}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3688kb
input:
2 5 1 1 1 1 1 2 0 2 0 2 7 3 1 2 3 2 1 4 2 0 0 0 0 0 2
output:
3 3
result:
ok 2 tokens
Test #2:
score: -100
Wrong Answer
time: 130ms
memory: 5636kb
input:
110121 5 0 0 0 0 0 1 4 5 4 1 5 1 0 0 0 0 0 6 8 6 1 5 2 0 0 0 0 4 4 1 3 6 5 3 0 0 0 0 5 1 1 7 6 5 4 0 0 0 0 6 8 7 0 8 5 5 0 0 0 0 5 9 7 7 5 5 6 0 0 0 0 9 2 2 8 0 5 7 0 0 0 0 9 4 7 0 9 5 8 0 0 0 0 6 7 3 7 5 5 9 0 0 0 0 4 0 9 1 4 5 0 1 0 0 0 0 6 6 3 0 5 1 1 0 0 0 3 4 3 4 9 5 2 1 0 0 0 0 4 0 1 4 5 3 1 0...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 376th words differ - expected: '3', found: '4'