#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 300000
typedef long long ll;
int N;
vector<int> C, D;
struct SEG{
SEG (int l, int r, ll mx) : l(l), r(r), mx(mx) {}
int l, r;
ll mx;
};
vector<SEG> seg;
void init(){
seg.push_back({-1, -1, 0});
}
void update(int idx, int s, int e, int x, ll y){
seg[idx].mx = max(seg[idx].mx, y);
if(s==e) return;
if(x<=(s+e)/2){
if(seg[idx].l==-1){
seg[idx].l = seg.size(); seg.push_back({-1, -1, 0});
}update(seg[idx].l, s, (s+e)/2, x, y);
}else{
if(seg[idx].r==-1){
seg[idx].r = seg.size(); seg.push_back({-1, -1, 0});
}update(seg[idx].r, (s+e)/2+1, e, x, y);
}
return;
}
ll max(int idx, int s, int e, int x, int y){
if(idx==-1) return 0;
if(x<=s && e<=y) return seg[idx].mx;
if(x>e || y<s) return 0;
return max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
}
struct S{
S(int x, int y, int idx1, int idx2, int type) : x(x), y(y), idx1(idx1), idx2(idx2), type(type) {}
int x, y;
int idx1, idx2;
int type;
bool operator <(const S &a)const{
if(y==a.y){
return x>a.x;
}return y<a.y;
}
};
vector<S> v;
ll ans[MAX_N+1];
ll cost[MAX_N+1][2];
int main(){
init();
scanf("%d", &N);
for(int i=0; i<N; i++){
int a;
scanf("%d", &a); C.push_back(a);
}
for(int i=0; i<N; i++){
int a; scanf("%d", &a); D.push_back(a);
}
for(int i=0; i<N; i++){
v.push_back({i, i, i, i, -1});
if(C[i]==1) continue;
if(i+C[i]-1 < N){
v.push_back({i, i+C[i]-1, i, 0, 1});
v.push_back({i+1, i+C[i]-1, i, 0, 2});
}
if(i-C[i]+1 >= 0){
v.push_back({i-C[i]+1, i, i, 1, 1});
v.push_back({i-C[i]+1, i-1, i, 1, 2});
}
}
sort(v.begin(), v.end());
while(!v.empty()){
S now = v.back(); v.pop_back();
//cout<<now.x<<' '<<now.y<<' '<<now.idx1<<' '<<now.idx2<<' '<<now.type<<endl;
if(now.type==-1){
ans[now.x] = max(0, 0, N-1, 0, now.x);
}else if(now.type==1){
cost[now.idx1][now.idx2] = max(0, 0, N-1, 0, now.x) + D[now.idx1];
}else if(now.type==2){
update(0, 0, N-1, now.x, cost[now.idx1][now.idx2]);
}
}
for(int i=0; i<N; i++){
if(C[i]==1) ans[i]+=(ll)D[i];
printf("%lld ", ans[i]);
}
return 0;
}
Compilation message
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
gorgeous.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a); C.push_back(a);
~~~~~^~~~~~~~~~
gorgeous.cpp:70:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a; scanf("%d", &a); D.push_back(a);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
