제출 #210733

#제출 시각아이디문제언어결과실행 시간메모리
210733mhy908Two Antennas (JOI19_antennas)C++14
100 / 100
847 ms54748 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define F first #define S second #define all(x) x.begin(), x.end() #define sortvec(x) sort(all(x)) #define compress(x) x.erase(unique(all(x)), x.end()) using namespace std; typedef long long LL; typedef pair<int, int> pii; typedef pair<LL, LL> pll; typedef pair<int, LL> pil; typedef pair<LL, int> pli; const LL llinf=987654321987654321; const int inf=2000000000; struct SEGMENT_TREE{ LL tree[800010], h[800010], lazy[800010]; void init(){ for(int i=1; i<800000; i++){ tree[i]=lazy[i]=-llinf; h[i]=llinf; } } void propogate(int point){ lazy[point*2]=max(lazy[point], lazy[point*2]); lazy[point*2+1]=max(lazy[point], lazy[point*2+1]); tree[point*2]=max(tree[point*2], lazy[point*2]-h[point*2]); tree[point*2+1]=max(tree[point*2+1], lazy[point*2+1]-h[point*2+1]); lazy[point]=-llinf; } void update(int point, int s, int e, int num, LL qu){ if(s==e){ h[point]=qu; lazy[point]=-llinf; return; } propogate(point); int mid=(s+e)/2; if(num<=mid)update(point*2, s, mid, num, qu); else update(point*2+1, mid+1, e, num, qu); tree[point]=max(tree[point*2], tree[point*2+1]); h[point]=min(h[point*2], h[point*2+1]); } void alter(int point, int s, int e, int a, int b, LL qu){ if(e<a||s>b)return; if(a<=s&&e<=b){ lazy[point]=max(lazy[point], qu); tree[point]=max(tree[point], qu-h[point]); return; } int mid=(s+e)/2; propogate(point); alter(point*2, s, mid, a, b, qu); alter(point*2+1, mid+1, e, a, b, qu); tree[point]=max(tree[point*2], tree[point*2+1]); } LL query(int point, int s, int e, int a, int b){ if(e<a||s>b)return -llinf; if(a<=s&&e<=b)return tree[point]; propogate(point); int mid=(s+e)/2; return max(query(point*2, s, mid, a, b), query(point*2+1, mid+1, e, a, b)); } }seg; int n, q; pii range[200010]; pii query[200010]; LL ans[200010], h[200010]; vector<pii> qu[200010], upd[200010]; void solve(){ for(int i=1; i<=n; i++){ qu[i].clear(); upd[i].clear(); } seg.init(); for(int i=1; i<=n; i++){ int t1=min(i+range[i].F, n+1); int t2=min(i+range[i].S, n)+1; upd[t1].pb(mp(i, 1)); upd[t2].pb(mp(i, 0)); } for(int i=1; i<=q; i++)qu[query[i].S].pb(mp(query[i].F, i)); for(int i=1; i<=n; i++){ for(auto j:upd[i]){ if(j.S)seg.update(1, 1, n, j.F, h[j.F]); else seg.update(1, 1, n, j.F, llinf); } if(i-range[i].F>=1){ seg.alter(1, 1, n, max(1, i-range[i].S), i-range[i].F, h[i]); } for(auto j:qu[i]){ //printf("query %d : %lld\n", j.S, seg.query(1, 1, n, j.F, i)); ans[j.S]=max(ans[j.S], seg.query(1, 1, n, j.F, i)); } } } int main(){ scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S); } scanf("%d", &q); for(int i=1; i<=q; i++){ scanf("%d %d", &query[i].F, &query[i].S); ans[i]=-1; } solve(); for(int i=1; i<=n; i++)h[i]=1000000000-h[i]; solve(); for(int i=1; i<=q; i++)printf("%lld\n", ans[i]); }

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

antennas.cpp: In function 'int main()':
antennas.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
antennas.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %d %d", &h[i], &range[i].F, &range[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
antennas.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &query[i].F, &query[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...