// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
const int Log = 20;
const int Inf = 1'000'000'001;
struct Fenwick {
ll fen[N];
Fenwick (){
memset(fen, 0, sizeof fen);
}
void Add(int idx, ll d){
for(; idx < N; idx += (idx & (-idx)))
fen[idx] += d;
}
ll Get(int idx){
ll res = 0;
for(; idx; idx -= (idx & (-idx)))
res += fen[idx];
return res;
}
void AddLR(int L, int R, ll d){
Add(L, d);
Add(R, -d);
}
};
Fenwick fr, fl;
int n, A[N];
pii sp[Log][N];
int BigR(int idx, pii V){
int res = idx;
for(int l = Log - 1; l >= 0; l--)
if(sp[l][res] <= V)
res += 1 << l;
return res;
}
int BigL(int idx, pii V){
int res = idx;
for(int l = Log - 1; l >= 0; l--)
if(sp[l][max(0, res - (1 << l) + 1)] <= V)
res -= 1 << l;
return res;
}
pii Max(int L, int R){
L ++;
pii res = {-1, -1};
for(int l = Log - 1; l >= 0; l--){
if(L + (1 << l) <= R){
res = max(res, sp[l][L]);
L += 1 << l;
}
}
return res;
}
int m;
int X[N], Y[N], C[N];
map<pii, vector<int> > mp;
map<pii, int> dp;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> A[i];
A[0] = A[n + 1] = Inf;
for(int i = 0; i <= n + 1; i++){
sp[0][i] = pii(A[i], i);
}
for(int l = 1; l < Log; l++)
for(int i = 0; i <= n + 1; i++)
sp[l][i] = max(sp[l - 1][i], sp[l - 1][min(n + 1, i + (1 << (l-1)) )] );
vector<pii> seg;
for(int i = 1; i <= n; i++){
//cerr << BigL(i, pii(A[i], i)) << ' ' << BigR(i, pii(A[i], i)) << '\n';
seg.pb({i, BigR(i, pii(A[i], i) )});
seg.pb({BigL(i, pii(A[i], i) ), i});
}
seg.pb({0, n + 1});
sort(all(seg)); seg.resize(unique(all(seg)) - seg.begin());
sort(all(seg), [&](pii A, pii B){
if(A.S - A.F == B.S - B.F) return A.F < B.F;
return A.S - A.F < B.S - B.F;
});
ll Sum = 0;
cin >> m;
for(int i = 1; i <= m; i++){
cin >> X[i] >> Y[i] >> C[i];
mp[pii( BigL(X[i], pii(Y[i], -1)), BigR(X[i], pii(Y[i], -1)) )].pb(i);
Sum += C[i];
}
//debug("Start");
ll res;
for(auto [L, R] : seg){
if(R - L == 1) continue;
int mx = Max(L, R).S;
res = dp[{L, mx}] + dp[{mx, R}];
vector<int> &V = mp[{L, R}];
for(auto st : V){
/*debug(st);
if(st == 4){
cerr << fr.Get(X[st]) << " " << fr.Get(R) << '\n';
cerr << "! " << st << " : " << (fr.Get(X[st]) - fr.Get(R)) << ", " << (fl.Get(X[st]) - fl.Get(L)) << '\n';
}*/
res = max(res, C[st] + (fr.Get(X[st]) - fr.Get(R)) + (fl.Get(X[st]) - fl.Get(L)) ) ;
}
dp[{L, R}] = res;
//cerr << L << "->" << R << " : " << res << '\n';
if(pii(L, R) == pii(0, n + 1)) continue;
if(pii(A[L], L) < pii(A[R], R) ){
//cerr << "# " << L << ' ' << R << ' ' << res << '\n';
fr.AddLR(BigL(L, pii(A[L], L)) + 1, L + 1, res);
} else {
fl.AddLR(R, BigR(R, pii(A[R], R)), res);
}
}
cout << Sum - dp[{0, n + 1}] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3840 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3840 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3840 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3712 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
