Submission #476606

#TimeUsernameProblemLanguageResultExecution timeMemory
476606cheissmartTwo Antennas (JOI19_antennas)C++14
0 / 100
1050 ms26076 KiB
#include <bits/stdc++.h> #pragma GCC optimize("trapv") #define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0); #define F first #define S second #define V vector #define PB push_back #define MP make_pair #define EB emplace_back #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m"; void DBG() { cerr << "]" << _reset << endl; } template<class H, class...T> void DBG(H h, T ...t) { cerr << to_string(h); if(sizeof ...(t)) cerr << ", "; DBG(t...); } #ifdef CHEISSMART #define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define debug(...) #endif const int INF = 1e9 + 7, N = 2e5 + 7; void cmax(int& a, int b) { a = max(a, b); } int h[N], a[N], b[N], l[N], r[N], ans[N]; vi G[N]; int n; int seg_a[N]; struct node { int base_mx, lz_mx, sum_mx; node(int base = -INF) { base_mx = base; lz_mx = -INF; sum_mx = base_mx + lz_mx; } } t[N * 4]; void pull(int v) { t[v].base_mx = max(t[v * 2].base_mx, t[v * 2 + 1].base_mx); t[v].sum_mx = max(t[v * 2].sum_mx, t[v * 2 + 1].sum_mx); } void apply(int v, int x) { cmax(t[v].sum_mx, t[v].base_mx + x); cmax(t[v].lz_mx, x); } void push(int v) { apply(v * 2, t[v].lz_mx); apply(v * 2 + 1, t[v].lz_mx); t[v].lz_mx = -INF; } void build(int v = 1, int tl = 0, int tr = n) { t[v] = node(); if(tr - tl == 1) return; int tm = (tl + tr) / 2; build(v * 2, tl, tm); build(v * 2 + 1, tm, tr); pull(v); } void activate(int pos, bool op, int v = 1, int tl = 0, int tr = n) { if(tr - tl == 1) { assert(tl == pos); if(op) t[v] = node(seg_a[tl]); else t[v] = node(); return; } push(v); int tm = (tl + tr) / 2; if(pos < tm) activate(pos, op, v * 2, tl, tm); else activate(pos, op, v * 2 + 1, tm, tr); pull(v); } void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = n) { if(l <= tl && tr <= r) { apply(v, x); return; } push(v); int tm = (tl + tr) / 2; if(l < tm) upd(l, r, x, v * 2, tl, tm); if(r > tm) upd(l, r, x, v * 2 + 1, tm, tr); pull(v); } int qry(int l, int r, int v = 1, int tl = 0, int tr = n) { if(l <= tl && tr <= r) return t[v].sum_mx; push(v); int tm = (tl + tr) / 2; int ans = -INF; if(l < tm) cmax(ans, qry(l, r, v * 2, tl, tm)); if(r > tm) cmax(ans, qry(l, r, v * 2 + 1, tm, tr)); return ans; } V<pair<int, bool>> ev[N]; signed main() { IO_OP; cin >> n; for(int i = 0; i < n; i++) { cin >> h[i] >> a[i] >> b[i]; } int q; cin >> q; for(int i = 0; i < q; i++) { cin >> l[i] >> r[i]; l[i]--, r[i]--; ans[i] = -1; } auto solve = [&] () { for(int i = 0; i < n; i++) { seg_a[i] = -h[i]; } build(); for(int i = 0; i < n; i++) { for(auto[x, y]:ev[i]) { activate(x, y); } int L = i - b[i], R = i - a[i]; if(R < 0) continue; L = max(L, 0); upd(L, R + 1, h[i]); for(int j:G[i]) { assert(r[j] == i); if(l[j] < R + 1) cmax(ans[j], qry(max(L, l[j]), R + 1)); } } }; auto solve1 = [&] () { for(int i = 0; i < q; i++) { assert(l[i] < r[i]); G[r[i]].PB(i); } for(int i = 0; i < n; i++) { int L = i + a[i], R = i + b[i]; if(L < n) { R = min(R, n - 1); ev[L].EB(i, true); if(R + 1 < n) ev[R + 1].EB(i, false); } } solve(); for(int i = 0; i < n; i++) h[i] *= -1; solve(); for(int i = 0; i < n; i++) { G[i].clear(); ev[i].clear(); } }; solve1(); reverse(h, h + n), reverse(a, a + n), reverse(b, b + n); for(int i = 0; i < q; i++) { l[i] = n - l[i] - 1, r[i] = n - r[i] - 1; swap(l[i], r[i]); } solve1(); for(int i = 0; i < q; i++) cout << ans[i] << '\n'; }

Compilation message (stderr)

antennas.cpp: In lambda function:
antennas.cpp:146:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |    for(auto[x, y]:ev[i]) {
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...