QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #232252 | #7616. Jump Graph | zhouxia | WA | 0ms | 3496kb | C++14 | 824b | 2023-10-30 08:45:50 | 2023-10-30 08:45:50 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
const int N=35;
int n,tp,a[N],l[N],r[N],st[N],p[N];
ll ls[N],rs[N],s[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
fr(i,1,n)cin>>a[i],p[a[i]]=i;
fr(i,1,n){
while(tp&&a[st[tp]]<a[i]){
r[st[tp]]=i,tp--;
}
l[i]=st[tp];
st[++tp]=i;
}
fr(i,1,tp)r[st[i]]=n+1;
// fr(i,1,n)cout<<l[i]<<" ";cout<<endl;
// fr(i,1,n)cout<<r[i]<<" ";cout<<endl;
fr(i,1,n){
int w=p[i];
ls[w-1]++;rs[w+1]++;
s[w]++;
if(a[l[w]]>a[r[w]]){
s[l[w]]+=s[w];
}else s[r[w]]+=s[w];
if(l[w])ls[l[w]-1]+=s[w];
rs[r[w]+1]+=s[w];
}
rf(i,n,1)ls[i]+=ls[i+1];
fr(i,1,n)rs[i]+=rs[i-1];
fr(i,1,n){cout<<ls[i]+rs[i]<<' ';}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3412kb
input:
6 1 6 3 2 5 4
output:
11 7 7 7 6 8
result:
ok single line: '11 7 7 7 6 8 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
2 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3400kb
input:
36 9 29 1 3 14 31 24 21 10 18 22 16 8 7 15 12 17 19 25 28 27 34 11 6 32 4 20 13 2 35 23 26 33 36 30 5
output:
9 6 5 5 7
result:
wrong answer 1st lines differ - expected: '92 89 90 90 91 78 73 71 71 71 ...110 107 136 136 137 136 168 168', found: '9 6 5 5 7 '