#include <bits/stdc++.h>
using namespace std;
struct stea{
int x, y, c;
};
int n, m;
stea a[200005];
bool active[200005];
set <pair <int, int> > ev[200005];
struct dsu{
int par[200005], sz[200005], st[200005], dr[200005];
long long val[200005];
void init(int n){
for(int i = 1; i <= n ; ++i){
par[i] = i; sz[i] = 1; val[i] = 0;
st[i] = dr[i] = i;
}
}
int find(int x){
if(x != par[x]) return (par[x] = find(par[x]));
return x;
}
void merge(int x, int y){
x = find(x); y = find(y);
if(x == y) return ;
if(sz[x] < sz[y]) swap(x, y);
par[y] = x;
sz[x] += sz[y];
val[x] += val[y];
st[x] = min(st[x], st[y]);
dr[x] = max(dr[x], dr[y]);
}
void update(long long cand, int x){
x = find(x);
val[x] = max(val[x], cand);
}
inline bool inside(int point, int wh){
wh = find(wh);
if(st[wh] <= point && point <= dr[wh]) return true;
return false;
}
};
dsu comp;
struct segTree{
long long lazy[800005];
void propag(int nod){
for(int i = nod * 2; i <= nod * 2 + 1 ; ++i) lazy[i] += lazy[nod];
lazy[nod] = 0;
}
void update(int x, int y, int val, int st = 1, int dr = n, int nod = 1){
if(x <= st && dr <= y){
lazy[nod] += val;
return ;
}
if(lazy[nod]) propag(nod);
int mij = (st + dr) / 2;
if(x <= mij) update(x, y, val, st, mij, nod * 2);
if(mij + 1 <= y) update(x, y, val, mij + 1, dr, nod * 2 + 1);
}
long long query(int x, int st = 1, int dr = n, int nod = 1){
if(st == dr) return lazy[nod];
if(lazy[nod]) propag(nod);
int mij = (st + dr) / 2;
if(x <= mij) return query(x, st, mij, nod * 2);
return query(x, mij + 1, dr, nod * 2 + 1);
}
};
segTree A;
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d", &n);
int x;
for(int i = 1; i <= n ; ++i){
scanf("%d", &x);
ev[x + 1].insert({0, i});
}
scanf("%d", &m);
long long Sum = 0;
for(int i = 1; i <= m ; ++i){
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
ev[a[i].y].insert({1, i});
Sum = Sum + a[i].c;
}
comp.init(n);
for(int i = 1; i <= n ; ++i){
int Last = -1;
long long sum = 0, Max = 0;
for(auto it : ev[i]){
int tip = it.first, pos = it.second;
if(tip == 0){
active[pos] = 1;
if(active[pos - 1]){
A.update(pos, pos, -comp.val[comp.find(pos - 1)]);
comp.merge(pos, pos - 1);
}
if(active[pos + 1]){
A.update(comp.st[comp.find(pos)], comp.dr[comp.find(pos)], -comp.val[comp.find(pos + 1)]);
A.update(comp.st[comp.find(pos + 1)], comp.dr[comp.find(pos + 1)], -comp.val[comp.find(pos)]);
comp.merge(pos, pos + 1);
}
}
else{
if(Last == -1) ;
else if(!comp.inside(a[pos].x, Last)){
int x = comp.find(Last);
comp.update(Max, Last);
sum = 0; Max = 0;
}
Last = a[pos].x;
sum = sum + a[pos].c;
Max = max(Max, a[pos].c - A.query(a[pos].x));
}
}
if(Last != -1){
int x = comp.find(Last);
comp.update(Max, Last);
}
}
for(int i = 1; i <= n ; ++i)
if(comp.dr[comp.find(i)] == i) Sum = Sum - comp.val[comp.find(i)];
printf("%lld", Sum);
return 0;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:131:25: warning: unused variable 'x' [-Wunused-variable]
int x = comp.find(Last);
^
constellation3.cpp:144:17: warning: unused variable 'x' [-Wunused-variable]
int x = comp.find(Last);
^
constellation3.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
constellation3.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
constellation3.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
constellation3.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
9856 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
9856 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
9856 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
