#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define pii pair < int, pi >
#define next next123
#define left left123
const int N = 2e5 + 7;
const ll INF = 1e18 + 7;
struct point{
int x, y, c;
} b[2 * N];
ll dp[N], g[8 * N];
int t[8 * N];
int a[N], next[N];
int n, m;
bool comp (point a, point b){
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
void build (int v, int l, int r){
if (l == r)
t[v] = a[l];
else {
int mid = (l + r) >> 1;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
t[v] = max(t[v + v], t[v + v + 1]);
}
}
int get (int v, int l, int r, int ql, int qr){
if (ql <= l && r <= qr)
return t[v];
if (r < ql || qr < l)
return 0;
int mid = (l + r) >> 1;
return max(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
}
void upd (int v, int l, int r, int pos, ll val){
if (l == r)
g[v] = min(val, g[v]);
else {
int mid = (l + r) >> 1;
if (pos <= mid)
upd(v + v, l, mid, pos, val);
else
upd(v + v + 1, mid + 1, r, pos, val);
g[v] = g[v + v] + g[v + v + 1];
}
}
ll get2 (int v, int l, int r, int ql, int qr){
if (ql <= l && r <= qr)
return g[v];
if (r < ql || qr < l)
return 0LL;
int mid = (l + r) >> 1;
return get2(v + v, l, mid, ql, qr) + get2(v + v + 1, mid + 1, r, ql, qr);
}
vi event[N];
vector < ll > cost[N];
main(){
cin >> n;
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
b[i] = {i, 0, 0};
}
cin >> m;
m += n;
build(1, 1, n);
for (int i = n + 1; i <= m; i++)
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].c);
sort(b + 1, b + m + 1, comp);
int l = 1;
ll s = 0;
for (int i = 1; i <= m; i++){
s += b[i].c;
if (b[i].x != b[i + 1].x){
for (l; l <= i; l++){
ll tmp;
if (cost[b[l].x].size())
tmp = cost[b[l].x].back();
else
tmp = INF;
cost[b[l].x].pb(min(s - b[l].c, tmp));
if (!b[l].y){
event[1].pb(b[l].x);
continue;
}
int ml = b[l].x, mr = n + 1;
while (ml + 1 < mr){
int mid = (ml + mr) >> 1;
if (get(1, 1, n, b[l].x, mid) >= b[l].y)
mr = mid;
else
ml = mid;
}
event[mr].pb(b[l].x);
}
l = i + 1;
s = 0;
}
}
memset(dp, 0x3f3f3f3f, sizeof(dp));
memset(g, 0x3f3f3f3f, sizeof(g));
dp[0] = 0;
int cur = 1;
for (int i = 1; i <= n; i++){
for (int it : event[i]){
upd(1, 1, n, it, cost[it][next[it]]);
next[it]++;
}
int cnt = 0;
for (cur; cur <= m && b[cur].x == i; cur++){
int l = 0, r = i;
while (l + 1 < r){
int mid = (l + r) >> 1;
if (get(1, 1, n, mid, i) >= b[cur].y)
l = mid;
else
r = mid;
}
ll res = dp[l] + cost[i][cnt];
if (l + 1 <= i - 1)
res += get2(1, 1, n, l + 1, i - 1);
dp[i] = min(dp[i], res);
cnt++;
}
while (b[cur].x == i || b[cur - 1].x != i);
}
cout << dp[n];
}
Compilation message
constellation3.cpp:83:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
constellation3.cpp: In function 'int main()':
constellation3.cpp:100:19: warning: statement has no effect [-Wunused-value]
for (l; l <= i; l++){
^
constellation3.cpp:135:17: warning: statement has no effect [-Wunused-value]
for (cur; cur <= m && b[cur].x == i; cur++){
^
constellation3.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
constellation3.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
