#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;
#define X first
#define Y second
const int inf = int(1e9)+ 7;
struct Star {
int x, y, c;
Star(int x, int y, int c) {
this->x = x;
this->y = y;
this->c = c;
}
};
struct SegmentTree {
int lv;
vector<ll> d;
SegmentTree(int n) {
lv = 2;
while(lv < n + 3)
lv *= 2;
d.resize(2 * lv + 2);
}
void insert(int a, int b, ll v) {
if(b < a)
return ;
int va = a + lv;
int vb = b + lv;
d[va] += v;
if(va != vb)
d[vb] += v;
while(va / 2 != vb / 2) {
if(va % 2 == 0)
d[va + 1] += v;
if(vb % 2 == 1)
d[vb - 1] += v;
va /= 2;
vb /= 2;
}
}
ll query(int x) {
int w = x + lv;
ll res = 0;
while(w) {
res += d[w];
w /= 2;
}
return res;
}
};
int n, m;
int a[200007];
int pl[200007], pr[200007];
int maxr[200007], maxl[200007];
vector<Star> St[200007];
struct Tree {
int jp[20][200007];
vector<int> ch[200007];
int ord[200007], max_ord[200007];
SegmentTree *ST;
int nxt_num;
void dfs(int w) {
ord[w] = nxt_num++;
for(int u : ch[w])
dfs(u);
max_ord[w] = nxt_num - 1;
}
Tree(int *p) {
for(int i = 1 ; i <= n ; i++) {
jp[0][i] = p[i];
ch[p[i]].push_back(i);
}
for(int j = 1 ; j <= 18 ; j++)
for(int i = 1 ; i <= n ; i++)
jp[j][i] = jp[j - 1][jp[j - 1][i]];
ST = new SegmentTree(n);
nxt_num = 0;
dfs(0);
}
int first_atleast(int i, int h) {
for(int j = 18 ; j >= 0 ; j--)
if(a[jp[j][i]] < h)
i = jp[j][i];
i = jp[0][i];
return i;
}
void insert(int i, ll v) {
ST->insert(ord[i], max_ord[i], v);
}
ll query(int a, int b) {
if(ord[a] > ord[b])
swap(a, b);
//a przodkiem b
return ST->query(ord[b]) - ST->query(a);
}
};
Tree *LT, *RT;
ll sum_all;
int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; i++)
scanf("%d", &a[i]);
a[0] = a[n + 1] = inf;
stack<int> S;
S.push(0);
for(int i = 1 ; i <= n ; i++) {
while(a[S.top()] <= a[i])
S.pop();
pl[i] = S.top();
maxr[S.top()] = i;
S.push(i);
}
while(!S.empty())
S.pop();
S.push(0);
for(int i = n ; i >= 1 ; i--) {
while(a[S.top()] <= a[i])
S.pop();
pr[i] = S.top();
maxl[S.top()] = i;
S.push(i);
}
LT = new Tree(pl);
RT = new Tree(pr);
scanf("%d", &m);
while(m--) {
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
sum_all += c;
int l = LT->first_atleast(x, y);
int r = RT->first_atleast(x, y);
if(a[l] <= a[r])
St[l].emplace_back(x, y, c);
if(a[r] <= a[l])
St[r].emplace_back(x, y, c);
//~ cout << l << endl;
}
vector<ii> V(n);
for(int i = 0 ; i < n ; i++)
V[i] = {a[i + 1], i + 1};
sort(V.begin(), V.end());
for(auto p : V) {
int i = p.Y;
ll dpl = LT->query(maxl[i], pl[i]) + RT->query(maxl[i], i);
ll dpr = LT->query(maxr[i], i) + RT->query(maxr[i], pr[i]);
for(auto s : St[i]) {
if(s.x > i)
dpr = max(dpr, (ll)s.c + LT->query(s.x, i) + RT->query(s.x, pr[i]));
else
dpl = max(dpl, (ll)s.c + LT->query(s.x, pl[i]) + RT->query(s.x, i));
}
LT->insert(i, dpl);
RT->insert(i, dpr);
//~ cout << i << " " << dpl << " " << dpr << endl;
}
//~ cout << maxr[0] << endl;
ll res = LT->query(maxr[0], 0) + RT->query(maxr[0], 0);
for(auto s : St[0]) {
res = max(res, (ll)s.c + LT->query(s.x, 0) + RT->query(s.x, 0));
}
printf("%lld\n", sum_all - res);
return 0;
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
constellation3.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
constellation3.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
constellation3.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
