제출 #613710

#제출 시각아이디문제언어결과실행 시간메모리
613710juggernautTwo Antennas (JOI19_antennas)C++14
13 / 100
3051 ms19748 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; typedef long long ll; typedef long double ld; template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef juggernaut #define printl(args...) printf(args) #else #define printl(args...) 0 #endif int h[200005]; int a[200005]; int b[200005]; const int inf=1e9; int ans[200005]; int n; vector<pair<int,int>>queries; int q; int lz[800005]; pair<int,int>tree[800005]; /*void build(int v,int l,int r){ if(l==r){ lz[v]=0; tree[v]={-inf,0}; return; } int mid=(l+r)>>1; build(v<<1,l,mid); build(v<<1|1,mid+1,r); tree[v]=max(tree[v<<1],tree[v<<1|1]); } void push(int &v,int &l,int &r){ if(l^r){ umax(lz[v<<1],lz[v]); umax(lz[v<<1|1],lz[v]); } lz[v]=0; } void st(int v,int l,int r,int pos,int val,int mx=0){ umax(mx,lz[v]); if(l==r){ tree[v]={mx-val,-mx}; lz[v]=0; return; }else{ umax(lz[v<<1],lz[v]); umax(lz[v<<1|1],lz[v]); } int mid=(l+r)>>1; if(pos<=mid)st(v<<1,l,mid,pos,val,mx); else st(v<<1|1,mid+1,r,pos,val,mx); tree[v]=max(tree[v<<1],tree[v<<1|1]); } void chmax(int v,int l,int r,int ql,int qr,int val){ if(qr<l||r<ql)return; if(ql<=l&&r<=qr){ umax(lz[v],val); if(-tree[v].sc<lz[v]){ int pivot=lz[v]+tree[v].sc; tree[v].sc-=pivot; tree[v].fr+=pivot; } return; } int mid=(l+r)>>1; chmax(v<<1,l,mid,ql,qr,val); chmax(v<<1|1,mid+1,r,ql,qr,val); tree[v]=max(tree[v<<1],tree[v<<1|1]); } int get(int v,int l,int r,int ql,int qr){ if(qr<l||r<ql)return -1; if(ql<=l&&r<=qr)return tree[v].fr; int mid=(l+r)>>1; return max(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid+1,r,ql,qr)); }*/ int x[200005]; int best[200005]; void build(int v,int l,int r){ for(int i=l;i<=r;i++){ x[i]=-inf; best[i]=-inf; } } void add(int v,int l,int r,int ql,int qr,int val){ for(int i=ql;i<=qr;i++){ x[i]+=val; umax(best[i],x[i]); } } int get(int v,int l,int r,int ql,int qr){ int ans=-1; for(int i=ql;i<=qr;i++)umax(ans,best[i]); return ans; } void solve(){ build(1,1,n); vector<vector<int>>inc(n+1),exc(n+1),query(n+1); for(int i=0;i<q;i++)query[queries[i].fr].push_back(i); for(int i=1;i<=n;i++){ if(i>a[i]){ exc[max(1,i-b[i])].push_back(i); inc[i-a[i]].push_back(i); } } for(int i=n;i;i--){ for(int idx:inc[i])add(1,1,n,idx,idx,inf-h[idx]); if(i+a[i]<=n) add(1,1,n,i+a[i],min(i+b[i],n),h[i]); if(i+a[i]<=n) add(1,1,n,i+a[i],min(i+b[i],n),-h[i]); for(int idx:query[i]) umax(ans[idx],get(1,1,n,i,queries[idx].sc)); for(int idx:exc[i])add(1,1,n,idx,idx,h[idx]-inf); } } 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=0;i^q;i++){ int l,r; scanf("%d%d",&l,&r); queries.emplace_back(l,r); ans[i]=-1; } solve(); reverse(h+1,h+1+n); reverse(a+1,a+1+n); reverse(b+1,b+1+n); for(auto &to:queries)to=make_pair(n-to.sc+1,n-to.fr+1); solve(); for(int i=0;i<q;i++)printf("%d\n",ans[i]); }

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

antennas.cpp: In function 'int main()':
antennas.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
antennas.cpp:121:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
antennas.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |   scanf("%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...