Submission #717512

#TimeUsernameProblemLanguageResultExecution timeMemory
717512walterwTwo Antennas (JOI19_antennas)C++17
22 / 100
2200 ms58296 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; #define int ll int H[200005], A[200005], B[200005]; struct event { int time, idx, height; bool add; bool operator<(event o) const { if (time == o.time) { if (!add) return true; return false; } return time < o.time; } }; vector<event> events; pair<int, int> vals[4 * 200005]; int ans[4 * 200005]; pair<int, int> qs[4 * 200005]; const pair<int, int> null = {1e16, 0}; void build() { fill(ans, ans+ 4 * 200005, -1); for (int i = 1; i < 4 * 200005; i++) { vals[i] = qs[i] = null; } } pair<int, int> comb(pair<int, int> a, pair<int, int> b) { return {min(a.first, b.first), max(a.second, b.second)}; } int eval(pair<int, int> vals, pair<int, int> qs) { int res = - 1; if (qs.first < (ll) 1e16) { if (vals.first < (ll) 1e16) res = max(res, abs(qs.first - vals.first)); if (vals.second > 0) res = max(res, abs(qs.first - vals.second)); } if (qs.second > 0) { if (vals.first < (ll) 1e16) res = max(res, abs(qs.second - vals.first)); if (vals.second > 0) res = max(res, abs(qs.second - vals.second)); } return res; } void push(int x) { if (qs[x] != null) { ans[2 * x] = max(ans[2 * x], eval(vals[2 * x], qs[x])); qs[2 * x] = comb(qs[2 * x], qs[x]); ans[2 * x + 1] = max(ans[2 * x + 1], eval(vals[2 * x + 1], qs[x])); qs[2 * x + 1] = comb(qs[2 * x + 1], qs[x]); qs[x] = null; } } void update(int x, int l, int r, int idx, int h) { if (l == r) { if (h) vals[x] = {h, h}; else vals[x] = {1e16, 0}; return; } push(x); int mid = (l + r) / 2; if (idx <= mid) update(2 * x, l, mid, idx, h); else update(2 * x + 1, mid + 1, r, idx, h); vals[x] = comb(vals[2 * x], vals[2 * x + 1]); ans[x] = max(ans[2 * x], ans[2 * x + 1]); } void updatequery(int x, int l, int r, int ql, int qr, int curh) { if (ql <= l && r <= qr) { // fully within ans[x] = max(ans[x], eval(vals[x], {curh, curh})); qs[x] = comb(qs[x], {curh, curh}); return; } if (l > qr || ql > r) return; int mid = (l + r) / 2; push(x); updatequery(2 * x, l, mid, ql, qr , curh); updatequery(2 * x + 1, mid + 1, r, ql, qr, curh); vals[x] = comb(vals[2 * x], vals[2 * x + 1]); ans[x] = max(ans[2 * x], ans[2 * x + 1]); } int query(int x, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return ans[x]; if (l > qr || ql > r) return -1; int mid = (l + r) / 2; push(x); return max(query(2 * x, l, mid, ql, qr), query(2 * x + 1, mid + 1, r, ql, qr)); } vector<pair<int, int>> queries[200005]; int toprint[200005]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> H[i] >> A[i] >> B[i]; } int q; cin >> q; for (int i = 1; i <= q; i++) { int a, b; cin >> a >> b; queries[b].emplace_back(a, i); } for (int i = 1; i <= n; i++) { events.push_back({i + A[i], i, H[i], true}); events.push_back({i + B[i] + 1, i, H[i], false}); } sort(events.begin(), events.end()); int idx = 0; build(); for (int i = 1; i <= n; i++) { while (idx < events.size() && events[idx].time == i) { if (events[idx].add) { update(1, 1, n, events[idx].idx, events[idx].height); } else { update(1, 1, n, events[idx].idx, 0); } idx++; } updatequery(1, 1, n, max((ll) 1, i - B[i]), max((ll) 1, i - A[i]), H[i]); for (auto [l, id] : queries[i]) { toprint[id] = query(1, 1, n, l, i); } } for (int i = 1; i <= q; i++) { cout << toprint[i] << "\n"; } }

Compilation message (stderr)

antennas.cpp: In function 'int32_t main()':
antennas.cpp:170:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         while (idx < events.size() && events[idx].time == 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...