제출 #122780

#제출 시각아이디문제언어결과실행 시간메모리
122780WhipppedCreamTwo Antennas (JOI19_antennas)C++17
22 / 100
578 ms40164 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 2e5+5; int n, q; int H[maxn], A[maxn], B[maxn]; int ql[maxn], qr[maxn]; ll res[maxn]; vector<int> buck[maxn]; vector<int> que[maxn]; ll tmp[maxn]; const int inf = 1234567890; struct segtree { struct node { ll a = -1, b = inf; ll res = -1; }; node st[4*maxn]; void clear() { for(int i = 1; i<= 4*n; i++) st[i] = node(); } void build(ll *arr, int p = 1, int L = 1, int R = n) { if(L == R) { st[p].a = arr[L]; return; } int M = (L+R)/2; build(arr, 2*p, L, M); build(arr, 2*p+1, M+1, R); } void modb(int p, ll x) { st[p].b = min(st[p].b, x); st[p].res = max(st[p].res, st[p].a-st[p].b); } void push(int p) { modb(2*p, st[p].b); modb(2*p+1, st[p].b); st[p].b = inf; } void update(int p) { st[p].a = max(st[2*p].a, st[2*p+1].a); st[p].res = max(max(st[p].res, st[2*p].res), max(st[2*p+1].res, st[p].a-st[p].b)); } void rngb(int i, int j, int dx, int p = 1, int L = 1, int R = n) { if(i> R || j< L) return; if(i<= L && R<= j) { modb(p, dx); return; } push(p); int M = (L+R)/2; rngb(i, j, dx, 2*p, L, M); rngb(i, j, dx, 2*p+1, M+1, R); update(p); } void pointa(int x, int dx, int p = 1, int L = 1, int R = n) { if(L == R) { st[p].a += dx; st[p].b = inf; return; } push(p); int M = (L+R)/2; if(x<= M) pointa(x, dx, 2*p, L, M); else pointa(x, dx, 2*p+1, M+1, R); update(p); } ll ask(int i, int j, int p = 1, int L = 1, int R = n) { if(i> R || j< L) return -1; if(i<= L && R<= j) return st[p].res; push(p); int M = (L+R)/2; ll x = ask(i, j, 2*p, L, M); ll y = ask(i, j, 2*p+1, M+1, R); return max(x, y); } }; segtree foo; void solve() { foo.clear(); for(int i = 1; i<= n; i++) buck[i].clear(); for(int i = 1; i<= n; i++) que[i].clear(); for(int i = 1; i<= n; i++) { buck[max(0, i-A[i])].pb(i); buck[max(0, i-B[i]-1)].pb(-i); } for(int i = 1; i<= q; i++) { que[ql[i]].pb(i); } for(int i = 1; i<= n; i++) tmp[i] = H[i]-inf; foo.build(tmp); for(int i = n; i>= 1; i--) { for(int x : buck[i]) { if(x> 0) foo.pointa(x, inf); else foo.pointa(-x, -inf); } foo.rngb(min(i+A[i], n), min(i+B[i], n), H[i]); for(int k : que[i]) { res[k] = max(res[k], foo.ask(ql[k], qr[k])); } } } int main() { scanf("%d", &n); for(int i = 1; i<= n; i++) { scanf("%d %d %d", &H[i], &A[i], &B[i]); } scanf("%d", &q); for(int i = 1; i<= q; i++) { scanf("%d %d", &ql[i], &qr[i]); } memset(res, -1, sizeof res); solve(); reverse(H+1, H+n+1); reverse(A+1, A+n+1); reverse(B+1, B+n+1); for(int i = 1; i<= q; i++) { int l = ql[i], r = qr[i]; ql[i] = n+1-r; qr[i] = n+1-l; } solve(); for(int i = 1; i<= q; i++) printf("%lld\n", res[i]); }

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

antennas.cpp: In function 'int main()':
antennas.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
antennas.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &H[i], &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
antennas.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &ql[i], &qr[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...