#include <bits/stdc++.h>
using namespace std;
int C[300005];
long long int D[300005];
long long int DP[1005][1005];
const long long int INF = 1e18;
struct SegTree {
struct Node {
long long int ma, p;
Node() : ma(0), p(0) {}
};
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
void prop(int n, int ns, int ne) {
if(seg[n].p) {
seg[n].ma += seg[n].p;
if(n<MAX/2) {
seg[2*n].p += seg[n].p;
seg[2*n+1].p += seg[n].p;
}
seg[n].p = 0;
}
}
void add(int s, int e, long long int k, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n].p += k;
prop(n,ns,ne);
return;
}
int mid = ns + ne >> 1;
add(s,e,k,2*n,ns,mid);
add(s,e,k,2*n+1,mid,ne);
if(n<MAX/2) seg[n].ma = max(seg[2*n].ma, seg[2*n+1].ma);
}
long long int sum(int s, int e, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return 0;
if(s<=ns&&ne<=e) return seg[n].ma;
int mid = ns + ne >> 1;
return max(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
}
};
typedef pair<long long int, long long int> P;
vector<long long int> Naive(int N) {
int i, j;
vector<long long int> ans;
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
for(int k = 0; k <= N; k++) DP[j][k] = -INF;
}
DP[i][i+1] = (C[i]==1 ? D[i] : 0);
for(int len = 1; len < N; len++) {
for(j=0;j+len<=N;j++) {
if(j+len+1<=N) {
DP[j][j+len+1] = max(DP[j][j+len+1], DP[j][j+len] + (C[j+len] == len + 1 ? D[j + len] : 0));
}
if(j >= 1) {
DP[j-1][j+len] = max(DP[j-1][j+len], DP[j][j+len] + (C[j-1] == len + 1 ? D[j-1] : 0));
}
}
}
ans.push_back(DP[0][N]);
}
return ans;
}
vector<vector<int>> adj;
int s[600005];
int e[600005];
int cnt = 0;
void dfs(int c) {
s[c] = cnt;
for(int n : adj[c]) dfs(n);
if(adj[c].size()==0) cnt++;
e[c] = cnt;
}
vector<long long int> NlogN_Solution(int N) {
int i, j;
vector<vector<array<long long int, 3>>> V1, V2;
V1.resize(N);
V2.resize(N);
vector<array<int, 3>> Node;
for(j=0;j<N;j++) {
if(C[j]!=1 && 0<=j-C[j]+1) {
Node.push_back({j-C[j]+1, j, 1});
V2[j-C[j]+1].push_back({j, D[j], Node.size() - 1});
}
if(j+C[j]-1<N) {
Node.push_back({j, j+C[j]-1, 0});
V1[j].push_back({j+C[j]-1, D[j], Node.size()-1});
}
}
adj.resize(Node.size());
set<P> tree1, tree2;
for(j=N-1;j>=0;j--) {
for(auto k : V1[j]) {
auto it1 = tree1.begin();
while(it1 != tree1.end()) {
if(it1->first >= k[0] + 1) break;
adj[k[2]].push_back(it1->second);
auto it2 = it1;
it1++;
tree1.erase(it2);
}
auto it2 = tree2.begin();
while(it2 != tree2.end()) {
if(it2->first >= k[0]+1) break;
adj[k[2]].push_back(it2->second);
auto it3 = it2;
it2++;
tree2.erase(it3);
}
tree1.insert(P(k[0], k[2]));
}
for(auto k : V2[j]) {
auto it1 = tree1.begin();
while(it1 != tree1.end()) {
if(it1->first >= k[0]) break;
adj[k[2]].push_back(it1->second);
auto it2 = it1;
it1++;
tree1.erase(it2);
}
auto it2 = tree2.begin();
while(it2 != tree2.end()) {
if(it2->first >= k[0]) break;
adj[k[2]].push_back(it2->second);
auto it3 = it2;
it2++;
tree2.erase(it3);
}
//tree2.Edit(k.first, max(val1, val2) + k.second);
tree2.insert(P(k[0], k[2]));
}
}
for(auto it : tree1) dfs(it.second);
for(auto it : tree2) dfs(it.second);
//cout << "Dfs Ordered\n";
SegTree tree(Node.size() + 5);
int MAX = tree.MAX;
vector<vector<array<long long int, 3>>> Qin, Qout;
Qin.resize(N);
Qout.resize(N);
for(i=0;i<N;i++) {
for(auto it : V1[i]) {
if(i==it[0]) continue;
if(i+1<N) Qin[i+1].push_back({s[it[2]], e[it[2]], +it[1]});
Qout[it[0]].push_back({s[it[2]], e[it[2]], -it[1]});
}
for(auto it : V2[i]) {
Qin[i].push_back({s[it[2]], e[it[2]], +it[1]});
if(it[0]-1>0) Qout[it[0]-1].push_back({s[it[2]], e[it[2]], -it[1]});
}
}
vector<long long int> ans;
for(i=0;i<N;i++) {
//cout << i << "th Turn\n";
for(auto it : Qin[i]) {
//cout <<"Plus : " << it[0] << ' ' << it[1] << ' ' <<it[2] << '\n';
tree.add(it[0], it[1], it[2], 1, 0, MAX/2);
}
long long int val = tree.sum(0, MAX/2, 1, 0, MAX/2) + (C[i]==1 ? D[i] : 0);
ans.push_back(val);
//cout << val << '\n';
for(auto it : Qout[i]) {
//cout << "Minus : " << it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
tree.add(it[0], it[1], it[2], 1, 0, MAX/2);
}
}
return ans;
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
int i, j;
for(i=0;i<N;i++) cin >> C[i];
for(i=0;i<N;i++) cin >> D[i];
/*for(i=0;i<N;i++) {
C[i] = rand() % (N/4) + 1;
}
for(i=0;i<N;i++) D[i] = rand() + 1;*/
vector<long long int> ans1 = NlogN_Solution(N);
for(i=0;i<N;i++) cout << ans1[i] << ' ';
}
Compilation message
gorgeous.cpp: In member function 'void SegTree::add(int, int, long long int, int, int, int)':
gorgeous.cpp:38:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = ns + ne >> 1;
| ~~~^~~~
gorgeous.cpp: In member function 'long long int SegTree::sum(int, int, int, int, int)':
gorgeous.cpp:47:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid = ns + ne >> 1;
| ~~~^~~~
gorgeous.cpp: In function 'std::vector<long long int> NlogN_Solution(int)':
gorgeous.cpp:93:58: warning: narrowing conversion of '(Node.std::vector<std::array<int, 3> >::size() - 1)' from 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
93 | V2[j-C[j]+1].push_back({j, D[j], Node.size() - 1});
| ~~~~~~~~~~~~^~~
gorgeous.cpp:97:57: warning: narrowing conversion of '(Node.std::vector<std::array<int, 3> >::size() - 1)' from 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
97 | V1[j].push_back({j+C[j]-1, D[j], Node.size()-1});
| ~~~~~~~~~~~^~
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:185:12: warning: unused variable 'j' [-Wunused-variable]
185 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
