#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
#define mp make_pair
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
#define ldb ldouble
typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
ll indt[1100000];
void update(int p, ll v) {
p += IT_MAX;
indt[p] = max(indt[p], v);
for (p /= 2; p; p /= 2) indt[p] = max(indt[2 * p], indt[2 * p + 1]);
}
ll getmx(int p1, int p2) {
p1 += IT_MAX;
p2 += IT_MAX;
ll rv = 0;
for (; p1 <= p2; p1 /= 2, p2 /= 2) {
if (p1 % 2 == 1) rv = max(rv, indt[p1++]);
if (p2 % 2 == 0) rv = max(rv, indt[p2--]);
}
return rv;
}
ll C[300050];
ll val[300050];
vector <pair<pll, pll>> Vl;
vector <pll> Vup;
ll ans[300050];
int main() {
int N, i;
scanf("%d", &N);
for (i = 1; i <= N; i++) scanf("%lld", &C[i]);
for (i = 1; i <= N; i++) scanf("%lld", &val[i]);
for (i = 1; i <= N; i++) {
pll u = pll(i, i);
if (C[i] == 1) Vl.emplace_back(pll(i, i), pll(0, val[i]));
else {
Vl.emplace_back(pll(i, i), pll(0, 0));
if (C[i] <= i) Vl.emplace_back(pll(i - C[i] + 1, i), pll(0, val[i]));
if (i + C[i] - 1 <= N) Vl.emplace_back(pll(i, i + C[i] - 1), pll(1, val[i]));
}
}
sort(all(Vl), [](auto a, auto b) {
pll u1 = a.first, u2 = b.first;
if (u1.first != u2.first) return u1.first < u2.first;
else return u1.second > u2.second;
});
for (int i = 0; i < Vl.size(); i++) {
auto it = Vl[i];
ll st = it.first.first, en = it.first.second;
ll type = it.second.first, v = it.second.second;
ll dpv = v + getmx(en, N);
if (st == en) ans[st] = dpv;
if (type == 0) update(en - 1, dpv);
else Vup.emplace_back(en, v);
if (i + 1 != Vl.size() && Vl[i].first.first != Vl[i + 1].first.first) {
for (auto it : Vup) update(it.first, it.second);
Vup.clear();
}
}
for (i = 1; i <= N; i++) printf("%lld ", ans[i]);
return !printf("\n");
}
Compilation message
gorgeous.cpp:23:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable:4996)
gorgeous.cpp:24:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK:336777216")
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:84:7: warning: variable 'u' set but not used [-Wunused-but-set-variable]
pll u = pll(i, i);
^
gorgeous.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Vl.size(); i++) {
~~^~~~~~~~~~~
gorgeous.cpp:109:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i + 1 != Vl.size() && Vl[i].first.first != Vl[i + 1].first.first) {
~~~~~~^~~~~~~~~~~~
gorgeous.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
gorgeous.cpp:80:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 1; i <= N; i++) scanf("%lld", &C[i]);
~~~~~^~~~~~~~~~~~~~~
gorgeous.cpp:81:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 1; i <= N; i++) scanf("%lld", &val[i]);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
524 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
552 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
524 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
552 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
524 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
552 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
