#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static unsigned char str[8800088], *p=str;
static ll __arrll[20000000], *__arrllp = __arrll;
inline ll* newll(const unsigned int SZ) {
__arrllp += SZ;
return __arrllp - SZ;
}
static int __arrint[20000000], *__arrintp = __arrint;
inline int* newint(const unsigned int SZ) {
__arrintp += SZ;
return __arrintp - SZ;
}
const int MAXN = 300005;
const int MX = 524288;
struct BIT {
ll *d;
int *XV;
int n, i;
void pushpoint() { n++; }
void precalpoint() {
if(!n) return;
XV = newint(n);
}
void push(int x) { XV[i++] = x; }
void precal() {
if(!n) return;
sort(XV, XV+n);
n = int(unique(XV, XV+n) - XV);
d = newll(n+1);
fill(d, d+n+1, 0);
}
void upd(int x, ll r) {
x = int(lower_bound(XV, XV+n, x) - XV) + 1;
for(; x <= n; x += rb(x))
if(d[x] < r) d[x] = r;
}
ll get(int x) {
x = int(upper_bound(XV, XV+n, x) - XV);
ll r = 0;
for(; 0 < x; x -= rb(x))
if(r < d[x]) r = d[x];
return r;
}
};
struct SEG {
BIT d[MX*2];
int mx;
void pushpoint(int x, int y) {
for(x += mx; x; x >>= 1)
d[x].pushpoint();
}
void precalpoint() {
for(int i = 1; i < mx*2; i++)
d[i].precalpoint();
}
void push(int x, int y) {
for(x += mx; x; x >>= 1)
d[x].push(y);
}
void precal() {
for(int i = 1; i < mx*2; i++)
d[i].precal();
}
void upd(int x, int y, ll r) {
for(x += mx; x; x >>= 1)
d[x].upd(y, r);
}
ll get(int s, int y) {
if(s < 0) return 0;
ll r = 0, t; int e = mx-1;
for(s += mx, e += mx; s <= e; s >>= 1, e >>= 1) {
if(s&1) {
t = d[s].get(y);
if(r < t) r = t;
s++;
}
if(~e&1) {
t = d[e].get(y);
if(r < t) r = t;
e--;
}
}
return r;
}
} seg;
struct EVT {
EVT(int s, int e, int x) : s(s), e(e), x(x) {}
int s, e, x;
inline void f(int &_s, int &_e, int &_x) const {
_s = s; _e = e; _x = x;
}
bool operator < (const EVT &t) const {
return (e-s) > (t.e-t.s);
}
};
vector<EVT> EV;
vector<pii> LV;
vector<int> LXV, LYV;
int A[MAXN], B[MAXN];
int N;
inline bool isGood(int s, int e) { return 1 <= s && s <= e && e <= N; }
int main() {
fread(str, 1, 8800088, stdin);
rf(N)
for(int i = 1; i <= N; i++) { rf(A[i]) }
for(int i = 1; i <= N; i++) { rf(B[i]) }
LV.eb(1, N);
for(int i = 1, s, e; i <= N; i++) {
s = i-A[i]+1; e = i-1;
if(isGood(s, e)) {
LV.eb(s, e);
EV.eb(s, e+1, i);
}
s = i+1; e = i+A[i]-1;
if(isGood(s, e)) {
LV.eb(s, e);
EV.eb(s-1, e, -i);
}
}
for(auto &v : LV) { LXV.eb(v.first); LYV.eb(v.second); }
sorv(LXV); univ(LXV); sorv(LYV); univ(LYV);
for(seg.mx = 1; seg.mx < sz(LXV); seg.mx <<= 1);
for(auto &v : LV) {
v.first = int(lower_bound(allv(LXV), v.first) - LXV.begin());
v.second = int(lower_bound(allv(LYV), v.second) - LYV.begin());
}
for(auto &v : LV) seg.pushpoint(v.second, v.first);
seg.precalpoint();
for(auto &v : LV) seg.push(v.second, v.first);
seg.precal(); sorv(EV);
for(auto &evt : EV) {
int s, e, idx, si, ei; evt.f(s, e, idx);
if(0 < idx) {
ei = int(lower_bound(allv(LYV), e) - LYV.begin());
si = int(upper_bound(allv(LXV), s) - LXV.begin()) - 1;
ll t = seg.get(ei, si) + B[idx];
ei = int(lower_bound(allv(LYV), e-1) - LYV.begin());
seg.upd(ei, si, t);
} else {
idx = -idx;
ei = int(lower_bound(allv(LYV), e) - LYV.begin());
si = int(upper_bound(allv(LXV), s) - LXV.begin()) - 1;
ll t = seg.get(ei, si) + B[idx];
si = int(upper_bound(allv(LXV), s+1) - LXV.begin()) - 1;
seg.upd(ei, si, t);
}
}
for(int i = 1; i <= N; i++) {
int ei = int(lower_bound(allv(LYV), i) - LYV.begin());
int si = int(upper_bound(allv(LXV), i) - LXV.begin()) - 1;
printf("%lld ", seg.get(ei, si) + (1 == A[i] ? B[i] : 0));
}
puts("");
return 0;
}
Compilation message
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:134:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(str, 1, 8800088, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
564 KB |
Output is correct |
| 4 |
Correct |
2 ms |
564 KB |
Output is correct |
| 5 |
Runtime error |
10 ms |
732 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
564 KB |
Output is correct |
| 4 |
Correct |
2 ms |
564 KB |
Output is correct |
| 5 |
Runtime error |
10 ms |
732 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
564 KB |
Output is correct |
| 4 |
Correct |
2 ms |
564 KB |
Output is correct |
| 5 |
Runtime error |
10 ms |
732 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
