Submission #126884

#TimeUsernameProblemLanguageResultExecution timeMemory
126884TadijaSebezTwo Antennas (JOI19_antennas)C++11
100 / 100
1169 ms49760 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long const int N=200050; const int M=2*N; const ll inf=1e18; int h[N],a[N],b[N]; ll ans[N]; vector<pair<int,int>> Qs[N]; vector<int> add[N],del[N]; int root,tsz,ls[M],rs[M]; ll mx1[M],mx2[M],lzy[M]; void Build(int &c, int ss, int se) { c=++tsz;mx1[c]=mx2[c]=lzy[c]=-inf; if(ss==se) return; int mid=ss+se>>1; Build(ls[c],ss,mid); Build(rs[c],mid+1,se); } void upd(int c, ll x) { mx2[c]=max(mx2[c],mx1[c]+x); lzy[c]=max(lzy[c],x); } void push(int c) { if(lzy[c]!=-inf) { upd(ls[c],lzy[c]); upd(rs[c],lzy[c]); lzy[c]=-inf; } } void Add(int c, int ss, int se, int qs, int qe, ll x) { if(qs>qe || qs>se || ss>qe) return; if(qs<=ss && qe>=se){ upd(c,x);return;} push(c); int mid=ss+se>>1; Add(ls[c],ss,mid,qs,qe,x); Add(rs[c],mid+1,se,qs,qe,x); mx2[c]=max(mx2[ls[c]],mx2[rs[c]]); } void Set(int c, int ss, int se, int qi, ll x) { if(ss==se){ mx1[c]=x;return;} push(c); int mid=ss+se>>1; if(qi<=mid) Set(ls[c],ss,mid,qi,x); else Set(rs[c],mid+1,se,qi,x); mx1[c]=max(mx1[ls[c]],mx1[rs[c]]); } ll Get(int c, int ss, int se, int qs, int qe) { if(qs>qe || qs>se || ss>qe) return -inf; if(qs<=ss && qe>=se) return mx2[c]; push(c); int mid=ss+se>>1; return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe)); } int n,q; void Solve() { Build(root,1,n); for(int i=1;i<=n;i++) { int l=i+a[i],r=i+b[i]; l=min(l,n+1); r=min(r,n+1); add[l].pb(i); del[r].pb(i); for(int x:add[i]) Set(root,1,n,x,h[x]); Add(root,1,n,i-b[i],i-a[i],-h[i]); for(auto t:Qs[i]) ans[t.second]=max(ans[t.second],Get(root,1,n,t.first,i)); for(int x:del[i]) Set(root,1,n,x,-inf); add[i].clear(); del[i].clear(); } for(int i=1;i<=tsz;i++) ls[i]=rs[i]=0; tsz=root=0; } int main() { int l,r; scanf("%i",&n); for(int i=1;i<=n;i++) scanf("%i %i %i",&h[i],&a[i],&b[i]); scanf("%i",&q); for(int i=1;i<=q;i++) scanf("%i %i",&l,&r),Qs[r].pb({l,i}),ans[i]=-1; Solve(); for(int i=1;i<=n;i++) h[i]=-h[i]; Solve(); for(int i=1;i<=q;i++) printf("%lld\n",ans[i]); return 0; }

Compilation message (stderr)

antennas.cpp: In function 'void Build(int&, int, int)':
antennas.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'void Add(int, int, int, int, int, long long int)':
antennas.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'void Set(int, int, int, int, long long int)':
antennas.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'long long int Get(int, int, int, int, int)':
antennas.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
antennas.cpp:88:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i %i",&h[i],&a[i],&b[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
antennas.cpp:90:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i %i",&l,&r),Qs[r].pb({l,i}),ans[i]=-1;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...