#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
#define MAXN 200005
#define LL long long
#define fi first
#define se second
using namespace std;
int N, M, A[MAXN], X[MAXN], Y[MAXN], C[MAXN];
int Start[MAXN], End[MAXN], Par[MAXN], Order[MAXN];
LL dp[MAXN], Ans;
vector <pair<int,int> > B, Star[MAXN]; //buildings
vector <int> adj[MAXN];
set<pair<int,int> > Active, S;
class fenwick {
LL BIT[MAXN];
void add(int p, LL x) {
for (; p<=N+3; p+=p&(-p)) {BIT[p]+=x;}
}
LL PrefSum(int p) {
LL res = 0;
for (; p>0; p-=p&(-p)) {res+=BIT[p];}
return(res);
}
public:
void upd(int l, int r, LL x) {
/*if (l > r) {return;}
add(l, x);
add(r+1, -x); */
for (int i=l; i<=r; i++) {BIT[i]+=x;}
}
LL ask(int p) {return(BIT[p]);} //point query
} FT;
LL slv(int u) { //cost to resolve the tree
dp[u] = C[u];
for (int v: adj[u]) {dp[u] += slv(v);}
dp[u] = min(dp[u], FT.ask(X[u]));
if (Par[u]) {
FT.upd(Start[u], End[u], C[u]);
FT.upd(Start[Par[u]], Start[u]-1, dp[u]);
FT.upd(End[u]+1, End[Par[u]], dp[u]);
}
return(dp[u]);
}
int main() {
//freopen("star3in.txt","r",stdin);
scanf("%d",&N);
for (int i=1; i<=N; i++) {
scanf("%d",&A[i]);
}
A[N+1] = 1 << 30;
B.push_back({2e9, 0});
scanf("%d",&M);
for (int i=1; i<=M; i++) {
scanf("%d %d %d",&X[i],&Y[i],&C[i]);
Star[X[i]].push_back({Y[i],i});
}
//find intervals
for (int i=1; i<=N+1; i++) {
while (B.size()&& B.back().fi <= A[i]) {B.pop_back();}
B.push_back({A[i],i});
for (auto s: Star[i]) {
int lo = -1, hi = B.size();
while (lo + 1 != hi) {
int mid = (lo + hi) >> 1;
if (B[mid].fi >= s.fi) {lo = mid;}
else {hi = mid;}
}
Start[s.se] = B[lo].se + 1;
Active.insert(s);
}
for (auto p = Active.begin(); p != Active.end(); ) {
auto P = *p;
if (P.fi > A[i]) {break;}
End[P.se] = i-1;
p = Active.erase(p);
}
}
//build MIS on tree
for (int i=1; i<=M; i++) {
Order[i] = i;
}
sort(Order+1, Order+M+1, [](int a, int b) {return(End[a] - Start[a] < End[b] - Start[b]);});
for (int i=1; i<=M; i++) { //bugged
auto pt = S.lower_bound({Start[Order[i]],-1});
while (pt != S.end() && (*pt).fi <= End[Order[i]]) {
Par[(*pt).se] = Order[i];
adj[Order[i]].push_back((*pt).se);
pt = S.erase(pt);
}
S.insert({Start[Order[i]], Order[i]});
}
//dp
for (int i=1; i<=M; i++) {
if (!Par[i]) {Ans += slv(i);}
}
printf("%lld", Ans);
}
Compilation message
constellation3.cpp: In function 'int main()':
constellation3.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
constellation3.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&A[i]);
~~~~~^~~~~~~~~~~~
constellation3.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&M);
~~~~~^~~~~~~~~
constellation3.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&X[i],&Y[i],&C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
