#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
long long a[212121];
struct xy {
long long t,x,y,c;
}all[414141]; long long an;
bool sort_y(xy a, xy b) {
if (a.y != b.y)return a.y > b.y;
if (a.t != b.y)return a.t < b.t;
return a.x < b.x;
}
set<pair<pair<long long, long long>, long long>>S; long long tn;
vector<long long>edge[414141];
vector<pair<long long, long long>>qr[414141];
long long S_start[414141], S_end[414141];
vector<long long>S_ER[414141]; long long point[414141];
void insert_S(long long s, long long e,long long parent) {
tn++;
S.insert({ { -s,e },tn });
S_start[tn] = s; S_end[tn] = e;
if (parent) edge[parent].push_back(tn);
}
int pp[414141][20];
long long sparse[414141][20];;
vector<int>need_to_fill[414141][20];
void init_sparse(long long w, long long bef) {
pp[w][0] = bef;
for (long long i = 0; pp[w][i] != -1; i++) {
need_to_fill[pp[w][i]][i].push_back(w);
pp[w][i + 1] = pp[pp[w][i]][i];
}
for (long long nxt : edge[w]) init_sparse(nxt, w);
}
long long D[414141], depth[414141], CS[414141];
void dfs(long long w,long long bef,long long dep) {
long long sum = 0;
depth[w] = dep;
for (long long nxt : edge[w]) {
dfs(nxt, w, dep + 1);
sum += D[nxt];
}
CS[w] = sum;
for (long long nxt : edge[w]) {
long long v = sum - D[nxt];
sparse[nxt][0] = v;
for (long long i = 1; i < 20; i++) {
for (long long who : need_to_fill[nxt][i]) {
long long p = pp[who][i - 1];
sparse[nxt][i] = sparse[p][i - 1] + sparse[who][i - 1];
}
}
}
long long qmax = 0;
for (auto q : qr[w]) {
long long res = q.second;
long long now = point[q.first];
res += CS[now];
for (long long i = 19; i >= 0; i--) {
long long nxt = pp[now][i];
if (nxt == -1 || depth[nxt] <= depth[w])continue;
res += sparse[now][i];
now = nxt;
}
res += sparse[now][0];
qmax = max(qmax, res);
}
D[w] = max(sum, qmax);
}
int main() {
long long n; scanf("%lld", &n);
long long i, j;
for (i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
all[an++] = { 1,i,a[i] };
}
long long m; scanf("%lld", &m);
long long allS = 0;
for (i = 1; i <= m; i++) {
all[an].t = 2;
scanf("%lld%lld%lld", &all[an].x, &all[an].y, &all[an].c);
allS += all[an].c;
an++;
}
sort(all, all + an, sort_y);
long long st, en;
insert_S(1, n, 0);
long long e9 = 1e9;
for (st = 0; st < an; st = en) {
for (en = st; all[st].y == all[en].y; en++);
// [st, en)
set<long long>erL;
for (i = st; i < en; i++) {
long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
if (t != 1) continue;
auto v = S.lower_bound({ { -x,-e9 },-e9 });
long long who = v->second;
S_ER[who].push_back(x);
erL.insert(who);
}
for (auto who : erL) {
long long s = S_start[who], e = S_end[who];
for (i = 0; i < S_ER[who].size(); i++) {
long long x = S_ER[who][i];
point[x] = who;
long long new_st = s, new_en = x - 1;
if (new_st <= new_en) insert_S(new_st, new_en, who);
s = x + 1;
if (i + 1 == S_ER[who].size()) {
if (s <= e) insert_S(s, e, who);
}
}
S.erase({ {-S_start[who],S_end[who] },who });
}
for (i = st; i < en; i++) {
long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
if (t != 2) continue;
auto v = S.lower_bound({ { -x,-e9 },-e9 });
if (v == S.end())continue;
long long who = v->second;
if(S_start[who] <= x && x <= S_end[who]) qr[who].push_back({ x, c });
}
}
for (i = 1; i <= tn; i++)for (j = 0; j < 20; j++)pp[i][j] = -1;
init_sparse(1, -1);
dfs(1, -1, 0);
printf("%lld\n", allS - D[1]);
return 0;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:96:42: warning: unused variable 'y' [-Wunused-variable]
96 | long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
| ^
constellation3.cpp:96:56: warning: unused variable 'c' [-Wunused-variable]
96 | long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
| ^
constellation3.cpp:105:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (i = 0; i < S_ER[who].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
constellation3.cpp:111:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | if (i + 1 == S_ER[who].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:118:42: warning: unused variable 'y' [-Wunused-variable]
118 | long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
| ^
constellation3.cpp:73:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | long long n; scanf("%lld", &n);
| ~~~~~^~~~~~~~~~~~
constellation3.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%lld", &a[i]);
| ~~~~~^~~~~~~~~~~~~~~
constellation3.cpp:79:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | long long m; scanf("%lld", &m);
| ~~~~~^~~~~~~~~~~~
constellation3.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%lld%lld%lld", &all[an].x, &all[an].y, &all[an].c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
224068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
224068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
144 ms |
224068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
