#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Star{
int x, y;
ll c;
Star(){}
bool operator<(const Star& b) const{
return y>b.y;
}
};
struct Node{
ll dp;
int anc;
int l, r;
vector<int> ch;
vector<Star> stars;
Node(int L, int R, int ANC){
l = L;
r= R;
dp =0;
anc = ANC;
}
};
vector<int> A;
vector<pair<int, int>> q;
vector<int> waiting;
vector<Node> tree;
vector<vector<Star>> S;
priority_queue<Star> cur_stars;
const int INF = 1000*1000*1000*2;
const int bar = (1<<18);
struct SNode{
ll delta;
SNode(ll d){
delta =d;
}
SNode(){
delta = 0;
}
};
vector<SNode> seg_tree(2*bar);
void add(int beg, int fin, ll val){
if(beg>=fin){
seg_tree[beg].delta += val;
}
else if(beg%2 == 1){
seg_tree[beg].delta += val;
add(beg+1, fin, val);
}
else if(fin%2== 0){
seg_tree[fin].delta += val;
add(beg, fin-1, val);
}
else{
add(beg/2, fin/2, val);
}
}
ll get(int id){
//cout<<"get "<<id<<endl;
id+= bar;
ll r= 0;
for(int i = id; i>0; i/=2){
r+=seg_tree[i].delta;
}
//cout<<r<<endl;
return r;
}
void update_waiting(pair<int, int> prev, int prev_id){
while(waiting.size()>0 && tree[waiting.back()].l >= prev.first+1){
auto child = waiting.back();
waiting.pop_back();
tree[child].anc = tree.size()-1;
tree.back().ch.push_back(child);
}
waiting.push_back(tree.size() -1);
}
void update_stars(int height, int id){
while(cur_stars.size()>0 && cur_stars.top().y<= height){
tree[id].stars.push_back(cur_stars.top());
//cout<<"star "<<cur_stars.top().y<<" "<<cur_stars.top().c<<endl;
cur_stars.pop();
}
}
void add_interval(int i){
auto prev= q.back();
//cout<<i<<" "<<prev.first<<" "<<prev.second<<endl;
if(prev.first < i-1){
tree.push_back(Node(prev.first+1, i-1, -1));
update_waiting(prev, tree.size()-1);
update_stars(min(prev.second, A[i]), tree.size()-1);
}
}
void DFS(int id){
////cout<<"started "<<tree[id].l<<" "<<tree[id].r<<endl;
ll total= 0;
for(auto child: tree[id].ch){
DFS(child);
total += tree[child].dp;
}
add(tree[id].l + bar, tree[id].r + bar, total);
for(auto child: tree[id].ch){
//cout<<"adding "<<tree[child].l<<" "<<tree[child].r<<total-tree[child].dp<<endl;
add(tree[child].l + bar, tree[child].r + bar, -tree[child].dp);
}
tree[id].dp = total;
for(auto s: tree[id].stars){
//cout<<"DFS star "<< s.c<<endl;
tree[id].dp = max(tree[id].dp, s.c +get(s.x));
}
//cout<<"id :"<<tree[id].l<<' '<<tree[id].r<<" "<<total<<' '<<tree[id].dp<<endl;
}
int main(){
int n;
cin>>n;
A.resize(n+2);
A[0] = INF;
A[n+1] = INF;
for(int i= 1; i<=n; i++){
cin>>A[i];
}
int m;
cin>>m;
S.resize(n+2);
ll sum_stars = 0;
for(int i = 0; i<m; i++){
Star s = Star();
cin>>s.x>>s.y>>s.c;
//cout<<s.x<<" "<<s.y<<" "<<s.c<<endl;
S[s.x].push_back(s);
sum_stars += s.c;
}
int cur = 0;
q.push_back(pair<int, int>(0,A[0]));
for(int i = 1; i<=n+1; i++){
int cur = A[i];
while(q.size()>0 && q.back().second<=cur){
add_interval(i);
q.pop_back();
}
//cout<<q.size()<<endl;
if(q.size()>0){
add_interval(i);
}
q.push_back(pair<int, int>(i, A[i]));
for(auto star: S[i]){
cur_stars.push(star);
}
}
int root= tree.size()-1;
DFS(root);
cout<<sum_stars -tree[root].dp<<endl;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:152:9: warning: unused variable 'cur' [-Wunused-variable]
152 | int cur = 0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4436 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
4 ms |
4436 KB |
Output is correct |
6 |
Correct |
3 ms |
4424 KB |
Output is correct |
7 |
Correct |
3 ms |
4424 KB |
Output is correct |
8 |
Correct |
3 ms |
4436 KB |
Output is correct |
9 |
Correct |
3 ms |
4424 KB |
Output is correct |
10 |
Correct |
4 ms |
4428 KB |
Output is correct |
11 |
Correct |
3 ms |
4428 KB |
Output is correct |
12 |
Correct |
3 ms |
4428 KB |
Output is correct |
13 |
Correct |
2 ms |
4436 KB |
Output is correct |
14 |
Correct |
3 ms |
4436 KB |
Output is correct |
15 |
Correct |
3 ms |
4420 KB |
Output is correct |
16 |
Correct |
3 ms |
4436 KB |
Output is correct |
17 |
Correct |
2 ms |
4428 KB |
Output is correct |
18 |
Correct |
3 ms |
4436 KB |
Output is correct |
19 |
Correct |
3 ms |
4436 KB |
Output is correct |
20 |
Correct |
2 ms |
4436 KB |
Output is correct |
21 |
Correct |
3 ms |
4436 KB |
Output is correct |
22 |
Correct |
4 ms |
4436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4436 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
4 ms |
4436 KB |
Output is correct |
6 |
Correct |
3 ms |
4424 KB |
Output is correct |
7 |
Correct |
3 ms |
4424 KB |
Output is correct |
8 |
Correct |
3 ms |
4436 KB |
Output is correct |
9 |
Correct |
3 ms |
4424 KB |
Output is correct |
10 |
Correct |
4 ms |
4428 KB |
Output is correct |
11 |
Correct |
3 ms |
4428 KB |
Output is correct |
12 |
Correct |
3 ms |
4428 KB |
Output is correct |
13 |
Correct |
2 ms |
4436 KB |
Output is correct |
14 |
Correct |
3 ms |
4436 KB |
Output is correct |
15 |
Correct |
3 ms |
4420 KB |
Output is correct |
16 |
Correct |
3 ms |
4436 KB |
Output is correct |
17 |
Correct |
2 ms |
4428 KB |
Output is correct |
18 |
Correct |
3 ms |
4436 KB |
Output is correct |
19 |
Correct |
3 ms |
4436 KB |
Output is correct |
20 |
Correct |
2 ms |
4436 KB |
Output is correct |
21 |
Correct |
3 ms |
4436 KB |
Output is correct |
22 |
Correct |
4 ms |
4436 KB |
Output is correct |
23 |
Correct |
5 ms |
4820 KB |
Output is correct |
24 |
Correct |
5 ms |
4820 KB |
Output is correct |
25 |
Correct |
5 ms |
4820 KB |
Output is correct |
26 |
Correct |
5 ms |
4780 KB |
Output is correct |
27 |
Correct |
6 ms |
4820 KB |
Output is correct |
28 |
Correct |
7 ms |
4820 KB |
Output is correct |
29 |
Correct |
5 ms |
4820 KB |
Output is correct |
30 |
Correct |
5 ms |
4816 KB |
Output is correct |
31 |
Correct |
6 ms |
4916 KB |
Output is correct |
32 |
Correct |
5 ms |
4948 KB |
Output is correct |
33 |
Correct |
6 ms |
4820 KB |
Output is correct |
34 |
Correct |
5 ms |
4820 KB |
Output is correct |
35 |
Correct |
7 ms |
4820 KB |
Output is correct |
36 |
Correct |
5 ms |
4900 KB |
Output is correct |
37 |
Correct |
5 ms |
4820 KB |
Output is correct |
38 |
Correct |
5 ms |
4944 KB |
Output is correct |
39 |
Correct |
5 ms |
4820 KB |
Output is correct |
40 |
Correct |
5 ms |
4948 KB |
Output is correct |
41 |
Correct |
5 ms |
4776 KB |
Output is correct |
42 |
Correct |
5 ms |
4820 KB |
Output is correct |
43 |
Correct |
6 ms |
4864 KB |
Output is correct |
44 |
Correct |
5 ms |
4820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4436 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
3 ms |
4436 KB |
Output is correct |
4 |
Correct |
3 ms |
4436 KB |
Output is correct |
5 |
Correct |
4 ms |
4436 KB |
Output is correct |
6 |
Correct |
3 ms |
4424 KB |
Output is correct |
7 |
Correct |
3 ms |
4424 KB |
Output is correct |
8 |
Correct |
3 ms |
4436 KB |
Output is correct |
9 |
Correct |
3 ms |
4424 KB |
Output is correct |
10 |
Correct |
4 ms |
4428 KB |
Output is correct |
11 |
Correct |
3 ms |
4428 KB |
Output is correct |
12 |
Correct |
3 ms |
4428 KB |
Output is correct |
13 |
Correct |
2 ms |
4436 KB |
Output is correct |
14 |
Correct |
3 ms |
4436 KB |
Output is correct |
15 |
Correct |
3 ms |
4420 KB |
Output is correct |
16 |
Correct |
3 ms |
4436 KB |
Output is correct |
17 |
Correct |
2 ms |
4428 KB |
Output is correct |
18 |
Correct |
3 ms |
4436 KB |
Output is correct |
19 |
Correct |
3 ms |
4436 KB |
Output is correct |
20 |
Correct |
2 ms |
4436 KB |
Output is correct |
21 |
Correct |
3 ms |
4436 KB |
Output is correct |
22 |
Correct |
4 ms |
4436 KB |
Output is correct |
23 |
Correct |
5 ms |
4820 KB |
Output is correct |
24 |
Correct |
5 ms |
4820 KB |
Output is correct |
25 |
Correct |
5 ms |
4820 KB |
Output is correct |
26 |
Correct |
5 ms |
4780 KB |
Output is correct |
27 |
Correct |
6 ms |
4820 KB |
Output is correct |
28 |
Correct |
7 ms |
4820 KB |
Output is correct |
29 |
Correct |
5 ms |
4820 KB |
Output is correct |
30 |
Correct |
5 ms |
4816 KB |
Output is correct |
31 |
Correct |
6 ms |
4916 KB |
Output is correct |
32 |
Correct |
5 ms |
4948 KB |
Output is correct |
33 |
Correct |
6 ms |
4820 KB |
Output is correct |
34 |
Correct |
5 ms |
4820 KB |
Output is correct |
35 |
Correct |
7 ms |
4820 KB |
Output is correct |
36 |
Correct |
5 ms |
4900 KB |
Output is correct |
37 |
Correct |
5 ms |
4820 KB |
Output is correct |
38 |
Correct |
5 ms |
4944 KB |
Output is correct |
39 |
Correct |
5 ms |
4820 KB |
Output is correct |
40 |
Correct |
5 ms |
4948 KB |
Output is correct |
41 |
Correct |
5 ms |
4776 KB |
Output is correct |
42 |
Correct |
5 ms |
4820 KB |
Output is correct |
43 |
Correct |
6 ms |
4864 KB |
Output is correct |
44 |
Correct |
5 ms |
4820 KB |
Output is correct |
45 |
Correct |
395 ms |
45168 KB |
Output is correct |
46 |
Correct |
390 ms |
44940 KB |
Output is correct |
47 |
Correct |
385 ms |
45368 KB |
Output is correct |
48 |
Correct |
387 ms |
44872 KB |
Output is correct |
49 |
Correct |
409 ms |
44952 KB |
Output is correct |
50 |
Correct |
331 ms |
44732 KB |
Output is correct |
51 |
Correct |
351 ms |
45072 KB |
Output is correct |
52 |
Correct |
352 ms |
45360 KB |
Output is correct |
53 |
Correct |
339 ms |
44968 KB |
Output is correct |
54 |
Correct |
400 ms |
54780 KB |
Output is correct |
55 |
Correct |
433 ms |
51648 KB |
Output is correct |
56 |
Correct |
401 ms |
50060 KB |
Output is correct |
57 |
Correct |
408 ms |
48816 KB |
Output is correct |
58 |
Correct |
379 ms |
51564 KB |
Output is correct |
59 |
Correct |
404 ms |
51552 KB |
Output is correct |
60 |
Correct |
318 ms |
56688 KB |
Output is correct |
61 |
Correct |
373 ms |
44540 KB |
Output is correct |
62 |
Correct |
423 ms |
55956 KB |
Output is correct |
63 |
Correct |
358 ms |
44612 KB |
Output is correct |
64 |
Correct |
326 ms |
44260 KB |
Output is correct |
65 |
Correct |
456 ms |
56084 KB |
Output is correct |
66 |
Correct |
342 ms |
44824 KB |
Output is correct |