QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #359238 | #7616. Jump Graph | zyz07 | WA | 2ms | 9888kb | C++17 | 1.0kb | 2024-03-20 15:10:22 | 2024-03-20 15:10:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=3e5+5;
int n,p[N],stk[N],ls[N],rs[N],siz[N];
ll ans[N],s1[N],s2[N];
void add(int l,int r,ll x){
ans[l]+=x;
ans[r+1]-=x;
}
void dfs(int u,int l,int r){
if(!u) return;
dfs(ls[u],l,u-1);
dfs(rs[u],u+1,r);
add(l,u,s2[rs[u]]+siz[rs[u]]);
add(u,r,s1[ls[u]]+siz[ls[u]]);
add(l,u-1,siz[rs[u]]+1);
add(u+1,r,siz[ls[u]]+1);
siz[u]=1+siz[ls[u]]+siz[rs[u]];
s1[u]=s1[ls[u]]+s1[rs[u]]+siz[ls[u]];
s2[u]=s2[ls[u]]+s2[rs[u]]+siz[rs[u]];
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
For(i,1,n){
cin>>p[i];
}
int top=0;
For(i,1,n){
int k=top;
for(;k&&p[stk[k]]<p[i];--k);
if(k) rs[stk[k]]=i;
if(k<top) ls[i]=stk[k+1];
stk[top=++k]=i;
}
dfs(stk[1],1,n);
For(i,1,n){
cout<<(ans[i]+=ans[i-1])<<" \n"[i==n];
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9832kb
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: 1ms
memory: 9768kb
input:
2 1 2
output:
1 1
result:
ok single line: '1 1'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 9888kb
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:
101 98 99 99 100 87 81 79 79 79 73 72 71 71 70 72 72 77 83 94 107 100 120 120 116 118 116 116 116 113 142 142 143 143 175 175
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: '101 98 99 99 100 87 81 79 79 7...116 113 142 142 143 143 175 175'