제출 #376956

#제출 시각아이디문제언어결과실행 시간메모리
376956pit4hTwo Antennas (JOI19_antennas)C++14
35 / 100
3002 ms108620 KiB
#include<bits/stdc++.h> #define st first #define nd second #define mp make_pair using namespace std; using pii = pair<int, int>; const int MAXN = 2e5+1; int n, q, h[MAXN], a[MAXN], b[MAXN]; int ans[MAXN]; vector<int> add[MAXN], del[MAXN]; vector<pii> queries[MAXN]; const int base = (1<<18); pii treeL[2*base+1], push[2*base+1]; set<pii> treeR[2*base+1]; int tree[2*base+1]; int get_min(int x) { if(treeR[x].empty()) return 0; int res = (*(treeR[x].begin())) . st; return res; } int get_max(int x) { if(treeR[x].empty()) return 0; int res = (*(treeR[x].rbegin())) . st; return res; } int eval(int id) { if(treeR[id].empty() || treeL[id].st==0) return -1; int res = max(abs(get_max(id) - treeL[id].st), abs(treeL[id].nd - get_min(id))); return res; } void upd(int x, int val) { if(val==0) return; if(treeL[x].st==0) treeL[x].st = val; treeL[x].st = min(treeL[x].st, val); treeL[x].nd = max(treeL[x].nd, val); tree[x] = max(tree[x], eval(x)); } void insR(int x, pii val, int id=1, int rl=0, int rr=base-1) { if(rl > x || rr < x) return; tree[id] = max(tree[id], eval(id)); treeR[id].insert(val); if(rl==x && rr==x) { treeL[id].st = treeL[id].nd = 0; return; } upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd); upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd); treeL[id].st = treeL[id].nd = 0; insR(x, val, id*2, rl, (rl+rr)/2); insR(x, val, id*2+1, (rl+rr)/2+1, rr); tree[id] = max(tree[id*2], tree[id*2+1]); } void delR(int x, pii val, int id=1, int rl=0, int rr=base-1) { if(rl > x || rr < x) return; tree[id] = max(tree[id], eval(id)); treeR[id].erase(val); if(rl==x && rr==x) { return; } upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd); upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd); delR(x, val, id*2, rl, (rl+rr)/2); delR(x, val, id*2+1, (rl+rr)/2+1, rr); tree[id] = max(tree[id*2], tree[id*2+1]); } void insL(int l, int r, int val, int id=1, int rl=0, int rr=base-1) { if(l > rr || r < rl) return; if(l<=rl && r>=rr) { upd(id, val); return; } upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd); upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd); insL(l, r, val, id*2, rl, (rl+rr)/2); insL(l, r, val, id*2+1, (rl+rr)/2+1, rr); tree[id] = max(tree[id*2], tree[id*2+1]); } int qry(int l, int r, int id=1, int rl=0, int rr=base-1) { if(l > rr || r < rl) return -1; if(l<=rl && r>=rr) { return max(tree[id], eval(id)); } upd(id*2, treeL[id].st), upd(id*2, treeL[id].nd); upd(id*2+1, treeL[id].st), upd(id*2+1, treeL[id].nd); return max(qry(l, r, id*2, rl, (rl+rr)/2), qry(l, r, id*2+1, (rl+rr)/2+1, rr)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int i=0; i<2*base; ++i) tree[i] = -1; cin>>n; for(int i=0; i<n; ++i) { cin>>h[i]>>a[i]>>b[i]; if(i-a[i]>=0) { add[i-a[i]].push_back(i); del[max(0, i-b[i])].push_back(i); } } cin>>q; for(int i=0; i<q; ++i) { int l, r; cin>>l>>r; queries[l-1].push_back(mp(r-1, i)); ans[i] = -1; } for(int i=n-1; i>=0; --i) { for(int j: add[i]) { insR(j, mp(h[j], j)); } if(i+a[i] < n) { insL(i+a[i], min(n-1, i+b[i]), h[i]); } for(auto& [j, id]: queries[i]) { ans[id] = qry(i, j); } for(int j: del[i]) { delR(j, mp(h[j], j)); } } for(int i=0; i<q; ++i) { cout<<ans[i]<<'\n'; } }

컴파일 시 표준 에러 (stderr) 메시지

antennas.cpp: In function 'int main()':
antennas.cpp:124:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |   for(auto& [j, id]: queries[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...