Submission #1170151

#TimeUsernameProblemLanguageResultExecution timeMemory
1170151M_W_13Two Antennas (JOI19_antennas)C++20
22 / 100
109 ms19984 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define st first #define nd second #define pb push_back const int MAXN = 1 << 18; ll seg1[2 * MAXN]; ll seg[2 * MAXN][2]; void upd2(int v, int c, ll x) { v += MAXN; seg[v][c] = x; v /= 2; while (v > 0) { seg[v][c] = max(seg[2 * v][c], seg[2 * v + 1][c]); v /= 2; } } ll query2(int l, int r, int c) { l += MAXN; r += MAXN; ll ans = -1e18; while (l < r) { if (l % 2 == 1) { ans = max(ans, seg[l][c]); l++; } if (r % 2 == 0) { ans = max(ans, seg[r][c]); r--; } l /= 2; r /= 2; } if (l == r) { ans = max(ans, seg[l][c]); } return ans; } void upd(int v, ll x) { v += MAXN; seg1[v] = max(seg1[v], x); v /= 2; while (v > 0) { seg1[v] = max(seg1[2 * v], seg1[2 * v + 1]); v /= 2; } } ll query(int l, int r) { l += MAXN; r += MAXN; ll ans = -1; while (l < r) { if (l % 2 == 1) { ans = max(ans, seg1[l]); l++; } if (r % 2 == 0) { ans = max(ans, seg1[r]); r--; } l /= 2; r /= 2; } if (l == r) { ans = max(ans, seg1[l]); } return ans; } struct ant { ll h; int a, b; }; ant T[MAXN]; struct pr { int l, r; int nr; }; ll spr(int x, int y) { if ((x + T[x].a <= y) && (x + T[x].b >= y) && (y - T[y].a >= x) && (y - T[y].b <= x)) { return abs(T[x].h - T[y].h); } return -1; } bool por(pr a, pr b) { return a.l < b.l; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); rep(i, 2 * MAXN) { seg1[i] = -1; seg[i][0] = -1e18; seg[i][1] = -1e18; } int n; cin >> n; rep(i, n) { cin >> T[i].h >> T[i].a >> T[i].b; } if (n <= 0) { int q; cin >> q; pr pyt[q]; rep(i, q) { cin >> pyt[i].l >> pyt[i].r; pyt[i].l = pyt[i].l - 1; pyt[i].r = pyt[i].r - 1; pyt[i].nr = i; } ll odp[q]; sort(pyt, pyt + q, por); int v = n - 1; for (int i = q - 1; i >= 0; i--) { while (v >= pyt[i].l) { for (int w = v + 1; w < n; w++) { upd(w, spr(v, w)); } v--; } odp[pyt[i].nr] = query(pyt[i].l, pyt[i].r); } rep(i, q) { cout << odp[i] << " "; } cout << '\n'; } else { int q; cin >> q; ll odp = -1; vector<pair<int, int>> zmiany; rep(i, n) { zmiany.pb({i + T[i].a, i}); zmiany.pb({i + T[i].b + 1, i}); } bool czyjest[n]; rep(i, n) { czyjest[i] = false; } sort(zmiany.begin(), zmiany.end()); int it = 0; int sz = zmiany.size(); rep(i, n) { while (it < sz && zmiany[it].st == i) { int v = zmiany[it].nd; if (czyjest[v]) { upd2(v, 0, -1e18); upd2(v, 1, -1e18); czyjest[v] = false; } else { upd2(v, 1, T[v].h); upd2(v, 0, -T[v].h); czyjest[v] = true; } it++; } int l = i - T[i].b; int r = i - T[i].a; if (r >= 0) { l = max(0, l); // cout << "i = " << i << " max = " << query2(l, r, 1) << " " << query2(l, r, 0) << '\n'; odp = max(odp, max(T[i].h + query2(l, r, 0), query2(l, r, 1) - T[i].h)); } } cout << odp << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...