제출 #200064

#제출 시각아이디문제언어결과실행 시간메모리
200064EntityITTwo Antennas (JOI19_antennas)C++14
0 / 100
410 ms30980 KiB
#include<bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define sz(x) ( (int)(x).size() ) using LL = long long; template<class T> inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; } template<class T> inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; } const int inf = 1e9 + 7; mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() ); int n; vector<tuple<int, int, int> > antennas; struct Node { int ans, mnH, mxH; Node(int _ans = -1, int _mnH = inf, int _mxH = -inf) : ans(_ans), mnH(_mnH), mxH(_mxH) {} Node operator + (const Node &_) const { return Node(max(ans, _.ans), min(mnH, _.mnH), max(mxH, _.mxH) );} }; struct Lz { int mnH, mxH; Lz(int _mnH = inf, int _mxH = -inf) : mnH(_mnH), mxH(_mxH) {} bool operator == (const Lz &_) const { return mnH == _.mnH && mxH == _.mxH; } Lz& operator += (const Lz& _) { asMn(mnH, _.mnH); asMx(mxH, _.mxH); return *this; } }; struct It { vector<Node> node; vector<Lz> lz; It(int nNode) { node.assign(nNode, Node() ); lz.assign(nNode, Lz() ); } void trueVal(int i, int Left, int Right) { if (lz[i] == Lz() ) return ; if (node[i].mnH < inf) { asMx(node[i].ans, abs(lz[i].mnH - node[i].mxH) ); asMx(node[i].ans, abs(lz[i].mxH - node[i].mnH) ); } if (Left != Right) { lz[i << 1] += lz[i]; lz[i << 1 | 1] += lz[i]; } lz[i] = Lz(); } void ins(int pos, int i = 1, int Left = 0, int Right = n - 1) { trueVal(i, Left, Right); if (pos < Left || Right < pos) return ; if (Left == Right) { node[i].mnH = node[i].mxH = get<0>(antennas[pos]); return ; } int Mid = (Left + Right) >> 1; ins(pos, i << 1, Left, Mid); ins(pos, i << 1 | 1, Mid + 1, Right); node[i] = node[i << 1] + node[i << 1 | 1]; } void era(int pos, int i = 1, int Left = 0, int Right = n - 1) { trueVal(i, Left, Right); if (pos < Left || Right < pos) return ; if (Left == Right) { node[i].mnH = node[i].mxH = get<0>(antennas[pos]); return ; } int Mid = (Left + Right) >> 1; era(pos, i << 1, Left, Mid); era(pos, i << 1 | 1, Mid + 1, Right); node[i] = node[i << 1] + node[i << 1 | 1]; } void upd(int l, int r, int h, int i = 1, int Left = 0, int Right = n - 1) { trueVal(i, Left, Right); if (r < Left || Right < l) return ; if (l <= Left && Right <= r) { lz[i] = Lz(h, h); trueVal(i, Left, Right); return ; } int Mid = (Left + Right) >> 1; upd(l, r, h, i << 1, Left, Mid); upd(l, r, h, i << 1 | 1, Mid + 1, Right); node[i] = node[i << 1] + node[i << 1 | 1]; } int getAns(int l, int r, int i = 1, int Left = 0, int Right = n - 1) { trueVal(i, Left, Right); if (r < Left || Right < l) return -1; if (l <= Left && Right <= r) return node[i].ans; int Mid = (Left + Right) >> 1; return max(getAns(l, r, i << 1, Left, Mid), getAns(l, r, i << 1 | 1, Mid + 1, Right) ); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef FourLeafClover freopen("input", "r", stdin); #endif // FourLeafCLover cin >> n; antennas.assign(n, {} ); vector<vector<pair<int, bool> > > change(n); for (int i = 0; i < n; ++i) { cin >> get<0>(antennas[i]) >> get<1>(antennas[i]) >> get<2>(antennas[i]); if (i + get<1>(antennas[i]) < n) change[i + get<1>(antennas[i])].emplace_back(i, true); if (i + get<2>(antennas[i]) + 1 < n) change[i + get<2>(antennas[i]) + 1].emplace_back(i, false); } int q; cin >> q; vector<vector<pair<int, int> > > que(n); for (int i = 0; i < q; ++i) { int l, r; cin >> l >> r; --l; --r; que[r].emplace_back(l, i); } It it( (n + 5) << 2); vector<int> ans(q); for (int r = 0; r < n; ++r) { for (auto _ : change[r]) { int pos = _.first; bool ins = _.second; if (ins) it.ins(pos); else it.era(pos); } it.upd(r - get<2>(antennas[r]), r - get<1>(antennas[r]), get<0>(antennas[r]) ); for (auto _ : que[r]) { int l = _.first, id = _.second; ans[id] = it.getAns(l, r); } } for (auto i : ans) cout << i << '\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...