제출 #389661

#제출 시각아이디문제언어결과실행 시간메모리
389661denkendoemeerTwo Antennas (JOI19_antennas)C++14
13 / 100
162 ms33220 KiB
#include<bits/stdc++.h> #define ll long long const int inf=1e9; using namespace std; int h[200005],a[200005],b[200005],ans[200005],ql[200005],qr[200005],lazy[550000],n; vector<int>t[200005],t1[200005],t2[200005]; array<int,2>aint[550000]; void upd(int nod,int x) { aint[nod][1]=max(aint[nod][0]+x,aint[nod][1]); lazy[nod]=max(lazy[nod],x); } void push(int nod) { upd(2*nod,lazy[nod]); upd(2*nod+1,lazy[nod]); lazy[nod]=-inf; } void update1(int nod,int st,int dr,int poz,int val) { if (st==dr){ aint[nod][0]=val; return ; } push(nod); int mij=(st+dr)/2; if (poz<=mij) update1(nod*2,st,mij,poz,val); else update1(nod*2+1,mij+1,dr,poz,val); aint[nod][0]=max(aint[nod*2][0],aint[nod*2+1][0]); aint[nod][1]=max(aint[nod*2][1],aint[nod*2+1][1]); } void update2(int nod,int st,int dr,int l,int r,int val) { if (l<=st && dr<=r){ upd(nod,val); return ; } int mij=(st+dr)/2; push(nod); if (l<=mij) update2(nod*2,st,mij,l,r,val); if (mij+1<=r) update2(nod*2+1,mij+1,dr,l,r,val); aint[nod][0]=max(aint[nod*2][0],aint[nod*2+1][0]); aint[nod][1]=max(aint[nod*2][1],aint[nod*2+1][1]); } int query(int nod,int st,int dr,int poz) { if (poz<=st) return aint[nod][1]; int mij=(st+dr)/2; push(nod); if (poz<=mij) return max(query(nod*2,st,mij,poz),query(nod*2+1,mij+1,dr,poz)); else return query(nod*2+1,mij+1,dr,poz); } void calc() { int i; for(i=0;i<550000;i++) aint[i][0]=aint[i][1]=lazy[i]=-inf-2; for(i=0;i<n;i++){ for(auto it:t1[i]) update1(1,0,n-1,it,-h[it]); if (i-a[i]>=0) update2(1,0,n-1,max(i-b[i],0),i-a[i],h[i]); for(auto it:t[i]) ans[it]=max(query(1,0,n-1,ql[it]),ans[it]); for(auto it:t2[i]) update1(1,0,n-1,it,-inf); } } int main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); int i; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d%d%d",&h[i],&a[i],&b[i]); t1[i+a[i]].push_back(i); t2[i+b[i]].push_back(i); } int q; scanf("%d",&q); memset(ans,-1,sizeof(ans)); for(i=0;i<q;i++){ scanf("%d%d",&ql[i],&qr[i]); ql[i]--; qr[i]--; t[qr[i]].push_back(i); } calc(); for(i=0;i<n;i++) h[i]=-h[i]; calc(); for(i=0;i<q;i++) printf("%d\n",ans[i]); return 0; }

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

antennas.cpp: In function 'int main()':
antennas.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
antennas.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         scanf("%d%d%d",&h[i],&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
antennas.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |         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...