Submission #1215207

#TimeUsernameProblemLanguageResultExecution timeMemory
1215207mychecksedadConstellation 3 (JOI20_constellation3)C++20
100 / 100
391 ms62160 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, a[N], m, L[N], R[N]; array<ll, 2> b[N]; vector<array<ll, 2>> V[N]; ll T[N], lazy[N]; // range max, range add void build(int sz){ for(int i = 0; i < 4*sz; ++i) T[i] = lazy[i] = 0; } void push(int k){ lazy[k<<1] += lazy[k]; lazy[k<<1|1] += lazy[k]; T[k<<1|1] += lazy[k]; T[k<<1] += lazy[k]; lazy[k] = 0; } void upd(int l, int r, int ql, int qr, int k, ll val){ if(ql > r || l > qr) return; if(ql <= l && r <= qr){ T[k] += val; lazy[k] += val; return; } push(k); int mid = l+r>>1; upd(l, mid, ql, qr, k<<1, val); upd(mid+1, r, ql, qr, k<<1|1, val); T[k] = max(T[k<<1], T[k<<1|1]); } ll get(int l, int r, int ql, int qr, int k){ if(ql > r || l > qr) return 0ll; if(ql <= l && r <= qr){ return T[k]; } push(k); int mid = l+r>>1; return max(get(l, mid, ql, qr, k<<1), get(mid+1, r, ql, qr, k<<1|1)); } void solve(){ cin >> n; for(int i = 1; i <= n; ++i){ cin >> a[i]; } L[1] = 0; for(int i = 2; i <= n; ++i){ L[i] = i - 1; while(L[i] > 0 && a[L[i]] <= a[i]) L[i] = L[L[i]]; } R[n] = n + 1; for(int i = n - 1; i >= 1; --i){ R[i] = i + 1; while(R[i] < n + 1 && a[R[i]] < a[i]) R[i] = R[R[i]]; } ll ans = 0; cin >> m; for(int i = 1; i <= m; ++i){ int x; cin >> x >> b[i][0] >> b[i][1]; V[x].pb({b[i][0], b[i][1]}); ans += b[i][1]; } vector<array<ll, 3>> pts; for(int i = 1; i <= n; ++i){ V[i].pb({a[i] + 1, 0}); sort(all(V[i])); vector<array<ll, 2>> TT; for(int j = 0; j < V[i].size(); ++j){ if(j == 0 || TT.back()[1] < V[i][j][1]) TT.pb(V[i][j]); } V[i].swap(TT); ll last = 0; for(auto [y, C]: V[i]){ pts.pb({y, C - last, i}); last = C; } } sort(all(pts)); build(n); for(auto [y, C, i]: pts){ if(y == a[i] + 1 && C == 0){ ll l_dp = get(1, n, L[i] + 1, i, 1); ll r_dp = get(1, n, i, R[i] - 1, 1); upd(1, n, L[i] + 1, i, 1, r_dp); upd(1, n, i, R[i] - 1, 1, l_dp); // cerr << y << ' ' << i << ' ' << l_dp << ' ' << r_dp } upd(1, n, i, i, 1, C); } cout << ans - T[1]; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...