제출 #158517

#제출 시각아이디문제언어결과실행 시간메모리
158517HungAnhGoldIBO2020Two Antennas (JOI19_antennas)C++14
100 / 100
1031 ms40396 KiB
#include<bits/stdc++.h> const int N=2e5+2; const int inf=1e9+7; using namespace std; vector<int> que_lis[N]; vector<pair<int,bool> > event[N]; int c[4*N],d[4*N],lazy[4*N],ar[N],ans[N],ranl[N],ranr[N]; pair<int,int> que[N]; void init(int idx,int l,int r){ c[idx]=-inf; d[idx]=-inf; lazy[idx]=-inf; if(l==r){ return; } int mid=(l+r)>>1; init(idx<<1,l,mid); init(idx<<1|1,mid+1,r); } void push(int idx,int l,int r){ lazy[idx<<1]=max(lazy[idx<<1],lazy[idx]); lazy[idx<<1|1]=max(lazy[idx<<1|1],lazy[idx]); d[idx<<1]=max(c[idx<<1]+lazy[idx<<1],d[idx<<1]); d[idx<<1|1]=max(c[idx<<1|1]+lazy[idx<<1|1],d[idx<<1|1]); lazy[idx]=-inf; } void upd(int idx,int l,int r,int pos,bool haiz){ if(l>pos||r<pos){ return; } if(l==r){ if(haiz){ c[idx]=ar[pos]; } else{ d[idx]=max(d[idx],c[idx]+lazy[idx]); c[idx]=-inf; } lazy[idx]=-inf; return; } if(lazy[idx]!=-inf){ push(idx,l,r); } int mid=(l+r)>>1; upd(idx<<1,l,mid,pos,haiz); upd(idx<<1|1,mid+1,r,pos,haiz); c[idx]=max(c[idx<<1],c[idx<<1|1]); d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1])); } void upd1(int idx,int l,int r,int lef,int rig,int val){ if(l>rig||r<lef){ return; } if(l>=lef&&r<=rig){ lazy[idx]=max(lazy[idx],val); val=-inf; if(l!=r){ val=max(d[idx<<1],d[idx<<1|1]); } d[idx]=max(max(c[idx]+lazy[idx],d[idx]),val); return; } if(lazy[idx]!=-inf){ push(idx,l,r); } int mid=(l+r)>>1; upd1(idx<<1,l,mid,lef,rig,val); upd1(idx<<1|1,mid+1,r,lef,rig,val); d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1])); } int getmax(int idx,int l,int r,int lef,int rig){ if(l>rig||r<lef){ return -inf; } if(l>=lef&&r<=rig){ return d[idx]; } if(lazy[idx]!=-inf){ push(idx,l,r); } int mid=(l+r)>>1; return max(getmax(idx<<1,l,mid,lef,rig),getmax(idx<<1|1,mid+1,r,lef,rig)); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n,i,j,k,l,q; cin>>n; init(1,1,n); for(i=1;i<=n;i++){ cin>>ar[i]>>ranl[i]>>ranr[i]; ranr[i]++; if(i+ranl[i]<=n){ event[i+ranl[i]].push_back({i,true}); } if(i+ranr[i]<=n){ event[i+ranr[i]].push_back({i,false}); } } cin>>q; for(i=1;i<=q;i++){ ans[i]=-1; cin>>que[i].first>>que[i].second; que_lis[que[i].second].push_back(i); } for(i=1;i<=n;i++){ for(j=0;j<event[i].size();j++){ upd(1,1,n,event[i][j].first,event[i][j].second); } if(i-ranl[i]>0){ upd1(1,1,n,max(1,i-ranr[i]+1),i-ranl[i],-ar[i]); } for(j=0;j<que_lis[i].size();j++){ // cout<<que_lis[i][j]<<' '<<getmax(1,1,n,que[que_lis[i][j]].first,i)<<endl; ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,que[que_lis[i][j]].first,i)); } event[i].clear(); que_lis[i].clear(); } init(1,1,n); for(i=n;i>=1;i--){ if(i-ranl[i]>0){ event[i-ranl[i]].push_back({i,true}); } if(i-ranr[i]>0){ event[i-ranr[i]].push_back({i,false}); } } for(i=1;i<=q;i++){ que_lis[que[i].first].push_back(i); } for(i=n;i>=1;i--){ for(j=0;j<event[i].size();j++){ upd(1,1,n,event[i][j].first,event[i][j].second); } if(i+ranl[i]<=n){ upd1(1,1,n,i+ranl[i],min(i+ranr[i]-1,n),-ar[i]); } for(j=0;j<que_lis[i].size();j++){ ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,i,que[que_lis[i][j]].second)); } } for(i=1;i<=q;i++){ cout<<ans[i]<<'\n'; } } /* 5 10 2 4 1 1 1 2 1 3 1 1 1 100 1 1 5 1 2 2 3 1 3 1 4 1 5 */

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

antennas.cpp: In function 'int main()':
antennas.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<event[i].size();j++){
           ~^~~~~~~~~~~~~~~~
antennas.cpp:114:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<que_lis[i].size();j++){
           ~^~~~~~~~~~~~~~~~~~
antennas.cpp:134:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<event[i].size();j++){
           ~^~~~~~~~~~~~~~~~
antennas.cpp:140:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<que_lis[i].size();j++){
           ~^~~~~~~~~~~~~~~~~~
antennas.cpp:88:12: warning: unused variable 'k' [-Wunused-variable]
  int n,i,j,k,l,q;
            ^
antennas.cpp:88:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l,q;
              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...