#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = LLONG_MAX;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 2e5+5;
vector<pii> stars[maxn]; // stars in my region
int lc[maxn], rc[maxn], par[maxn];
int fa[21][maxn];
int L[maxn], R[maxn];
bool on[maxn];
namespace DSU{
int par[maxn];
int find(int x) {
return x == par[x]? x : par[x] = find(par[x]);
}
void mrg(int a, int b) { // a is the new head
a = find(a); b = find(b);
MN(L[a], L[b]); MX(R[a], R[b]);
par[b] = a;
}
};
int a[maxn];
ll dp[maxn];
ll s[maxn];
void MO(int e, ll v) {
for(++e; e<maxn; e+=e&-e) s[e] += v;
}
ll QU(int e) {
ll re = 0;
for(++e; e>0; e-=e&-e) {
re += s[e];
}
return re;
}
signed main(){
IOS();
int n; cin>>n;
vector<pii> who;
REP(i,n) {
cin>>a[i]; who.pb({a[i], i}); par[i] = L[i] = R[i] = i;
}
sort(ALL(who), [&](pii x, pii y){return x.f==y.f?x.s>y.s:x.f<y.f;});
for(pii p : who) {
int i = p.s;
lc[i] = rc[i] = n+1;
if(i && on[i-1]) {
lc[i] = DSU::find(i-1); par[lc[i]] = i;
DSU::mrg(i, i-1);
}
if(i!=n-1 && on[i+1]) {
rc[i] = DSU::find(i+1); par[rc[i]] = i;
DSU::mrg(i, i+1);
}
on[i] = 1;
}
for(int j = 0; j<20; ++j) {
REP(i,n) {
if(j == 0) fa[j][i] = par[i];
else fa[j][i] = fa[j-1][fa[j-1][i]];
}
}
int m; cin>>m;
ll sig = 0;
REP(i,m) {
int x,y,v; cin>>x>>y>>v; --x; sig += v;
int at = x;
for(int j = 19; j>=0; --j) {
if(a[fa[j][at]] < y) at = fa[j][at];
}
bug(i, at, fa[0][at]);
stars[at].pb({x,y});
}
REP(ind,n) {
int i = who[ind].s;
dp[i] = dp[lc[i]] + dp[rc[i]];
for(pii S : stars[i]) {
if(S.f == i) {
MX(dp[i], dp[lc[i]] + dp[rc[i]] + S.s);
}else if (S.f < i) {
MX(dp[i], QU(S.f) + dp[rc[i]] + S.s);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
