QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#229012 | #7616. Jump Graph | PBY | WA | 4ms | 23220kb | C++14 | 1.9kb | 2023-10-28 14:49:05 | 2023-10-28 14:49:05 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n;
int a[N];
int deg[N],fa[N];
int st[N][25];
ll siz[N],d[N];
ll tree[N];
bool ins[N];
vector<int> e[N];
int get(int l,int r){
int p=log2(r-l+1);
return max(st[l][p],st[r-(1<<p)+1][p]);
}
int lowbit(int x){
return x&(-x);
}
void add(int x,ll w){
for(;x<=n;x+=lowbit(x))
tree[x]+=w;
}
ll ask(int x){
ll rs=0;
for(;x;x-=lowbit(x))
rs+=tree[x];
return rs;
}
void dfs(int k){
d[k]=0;
siz[k]=1;
ins[k]=true;
for(int to:e[k]){
if(ins[to]) continue;
dfs(to);
d[k]+=d[to];
siz[k]+=siz[to];
}
d[k]+=siz[k];
if(fa[k]<k) add(max(fa[k],1),d[k]),add(k,-d[k]);
else add(k+1,d[k]),add(fa[k]+1,-d[k]);
return ;
}
void settle1(){
for(int i=1;i<=n;i++){
int l=1,r=i-1;
while(l<=r){
int mid=(l+r)>>1;
if(get(mid,i-1)>=a[i]) fa[i]=mid,l=mid+1;
else r=mid-1;
}
}
return ;
}
void settle2(){
for(int i=n;i>=1;i--){
int l=i+1,r=n;fa[i]=0;
while(l<=r){
int mid=(l+r)>>1;
if(get(i+1,mid)>=a[i]) fa[i]=mid,r=mid-1;
else l=mid+1;
}
if(!fa[i]) fa[i]=n+1;
}
return ;
}
void solve(){
// for(int i=1;i<=n;i++)
// cout<<fa[i]<<' ';cout<<'\n';
for(int i=1;i<=n;i++)
deg[i]=ins[i]=0,e[i].clear();
for(int i=1;i<=n;i++)
if(fa[i]>0&&fa[i]<=n)
e[fa[i]].push_back(i),deg[i]++;
for(int i=1;i<=n;i++)
if(!deg[i]) dfs(i);
// for(int i=1;i<=n;i++)
// cout<<ask(i)<<' ';cout<<"\n\n";
return ;
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) st[i][0]=a[i];
for(int k=1;(1<<k)<=n;k++)
for(int i=1;i+(1<<k)-1<=n;i++)
st[i][k]=max(st[i][k-1],st[i+(1<<k-1)][k-1]);
settle1(),solve();
settle2(),solve();
for(int i=1;i<=n;i++)
cout<<ask(i)<<' ';
return 0;
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 20696kb
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: 3ms
memory: 19528kb
input:
2 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 23220kb
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...16 113 142 142 143 143 175 175 '