Submission #122794

#TimeUsernameProblemLanguageResultExecution timeMemory
122794WhipppedCreamTwo Antennas (JOI19_antennas)C++17
22 / 100
527 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 = 0; i<= 4*n; i++) { st[i] = node(); assert(st[i].a == -1); } } 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) { assert(st[p].b == inf); 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, ll 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, ll 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]+1)].pb(i); buck[max(0, i-B[i])].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]-1e9; foo.build(tmp); for(int i = n; i>= 1; i--) { 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])); } for(int x : buck[i]) { if(x> 0) foo.pointa(x, 1e9); else foo.pointa(-x, -1e9); } } } 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; assert(ql[i]<= qr[i]); } solve(); for(int i = 1; i<= q; i++) printf("%lld\n", res[i]); }

Compilation message (stderr)

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