#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
int a[212121];
struct xy {
int t,x,y,c;
}all[414141]; int an;
bool sort_y(xy a, xy b) {
if (a.y != b.y)return a.y > b.y;
if (a.t != b.t)return a.t < b.t;
return a.x < b.x;
}
set<pair<pair<int, int>, int>>S; int tn;
vector<int>edge[414141];
vector<pair<int, int>>qr[414141];
int S_start[414141], S_end[414141];
vector<int>S_ER[414141]; int point[414141];
void insert_S(int s, int e,int 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(int w, int bef) {
pp[w][0] = bef;
for (int 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 (int nxt : edge[w]) init_sparse(nxt, w);
}
long long D[414141], depth[414141], CS[414141];
void dfs(int w,int bef,int dep) {
long long sum = 0;
depth[w] = dep;
for (int nxt : edge[w]) {
dfs(nxt, w, dep + 1);
sum += D[nxt];
}
CS[w] = sum;
for (int nxt : edge[w]) {
long long v = sum - D[nxt];
sparse[nxt][0] = v;
for (int i = 1; i < 18; i++) {
for (int who : need_to_fill[nxt][i]) {
int p = pp[who][i - 1];
sparse[who][i] = sparse[p][i - 1] + sparse[who][i - 1];
}
}
}
long long qmax = 0;
for (auto q : qr[w]) {
long long res = q.second;
int now = point[q.first];
res += CS[now];
for (int i = 18; i >= 0; i--) {
int nxt = pp[now][i];
if (nxt == -1 || depth[nxt] <= depth[w])continue;
res += sparse[now][i];
now = nxt;
}
if(now!=w)res += sparse[now][0];
qmax = max(qmax, res);
}
D[w] = max(sum, qmax);
}
int ck[414141];
vector<int>erL;
int main() {
int n; scanf("%d", &n);
int i, j;
for (i = 1; i <= n; i++) {
scanf("%d", &a[i]);
all[an++] = { 1,i,a[i],0 };
}
int m; scanf("%d", &m);
long long allS = 0;
for (i = 1; i <= m; i++) {
all[an].t = 2;
scanf("%d%d%d", &all[an].x, &all[an].y, &all[an].c);
allS += all[an].c;
an++;
}
sort(all, all + an, sort_y);
int st, en;
insert_S(1, n, 0);
int e9 = 1e9;
for (st = 0; st < an; st = en) {
for (en = st; all[st].y == all[en].y; en++);
// [st, en)
for (i = st; i < en; i++) {
int 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 });
int who = v->second;
S_ER[who].push_back(x);
ck[who] = 1;
if(ck[who]==0) erL.push_back(who);
}
for (auto who : erL) {
int s = S_start[who], e = S_end[who];
for (i = 0; i < S_ER[who].size(); i++) {
int x = S_ER[who][i];
point[x] = who;
int 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);
}
}
ck[who] = 0;
S.erase({ {-S_start[who],S_end[who] },who });
}
erL.clear();
for (i = st; i < en; i++) {
int 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;
int 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:100:36: warning: unused variable 'y' [-Wunused-variable]
100 | int t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
| ^
constellation3.cpp:100:50: warning: unused variable 'c' [-Wunused-variable]
100 | int t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
| ^
constellation3.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (i = 0; i < S_ER[who].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
constellation3.cpp:116:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | if (i + 1 == S_ER[who].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:125:36: warning: unused variable 'y' [-Wunused-variable]
125 | int t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
| ^
constellation3.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | int n; scanf("%d", &n);
| ~~~~~^~~~~~~~~~
constellation3.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
constellation3.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | int m; scanf("%d", &m);
| ~~~~~^~~~~~~~~~
constellation3.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d%d%d", &all[an].x, &all[an].y, &all[an].c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
223936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
223936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
223936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
