Submission #592671

#TimeUsernameProblemLanguageResultExecution timeMemory
592671andrei_boacaNuclearia (CEOI15_nuclearia)C++14
25 / 100
1098 ms238472 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("O3") using namespace std; typedef long long ll; typedef long double ld; vector<vector<ll>> v; int n,m,k,q; int nradds=0; void add(int x1,int y1,int x2,int y2,ll val) { x1=max(x1,1); y1=max(y1,1); x2=min(x2,n); y2=min(y2,m); v[x1][y1]+=val; v[x2+1][y1]-=val; v[x1][y2+1]-=val; v[x2+1][y2+1]+=val; } ll getsum(int x1,int y1,int x2,int y2) { return v[x2][y2]-v[x1-1][y2]-v[x2][y1-1]+v[x1-1][y1-1]; } vector<ll> arb,toprop[2]; void prop(ll nod,ll st,ll dr) { ll v0=toprop[0][nod],v1=toprop[1][nod]; int mij=(st+dr)/2; arb[nod*2]+=v0*(mij-st+1); arb[nod*2]+=v1*((st+mij)*(mij-st+1)/2); arb[nod*2+1]+=v0*(dr-(mij+1)+1); arb[nod*2+1]+=v1*(((mij+1)+dr)*(dr-(mij+1)+1)/2); toprop[0][nod*2]+=v0; toprop[1][nod*2]+=v1; toprop[0][nod*2+1]+=v0; toprop[1][nod*2+1]+=v1; toprop[0][nod]=0; toprop[1][nod]=0; } void update(ll nod,ll st,ll dr,ll a,ll b,ll v0,ll v1) { if(st!=dr) prop(nod,st,dr); if(st>=a&&dr<=b) { arb[nod]+=v0*(dr-st+1); arb[nod]+=v1*((st+dr)*(dr-st+1)/2); toprop[0][nod]+=v0; toprop[1][nod]+=v1; return; } ll mij=(st+dr)/2; if(a<=mij) update(nod*2,st,mij,a,b,v0,v1); if(b>mij) update(nod*2+1,mij+1,dr,a,b,v0,v1); arb[nod]=arb[nod*2]+arb[nod*2+1]; } ll query(int nod,int st,int dr,int a,int b) { if(st!=dr) prop(nod,st,dr); if(st>=a&&dr<=b) return arb[nod]; ll rez=0; ll mij=(st+dr)/2; if(a<=mij) rez+=query(nod*2,st,mij,a,b); if(b>mij) rez+=query(nod*2+1,mij+1,dr,a,b); return rez; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>k; if(m==1) { arb.resize(4*n+5); for(int i=0;i<=1;i++) toprop[i].resize(4*n+5); for(int z=1;z<=k;z++) { ll x,y,a,b; cin>>x>>y>>a>>b; assert(y==1); ll nr=a/b; update(1,1,n,x,x,a,0); ll st=x-nr; ll dr=x-1; if(dr>0&&st<=dr) { st=max(st,1LL); update(1,1,n,st,dr,a-(dr+1)*b,+b); } st=x+1; dr=x+nr; if(st<=n&&st<=dr) { dr=min(dr,n*1LL); update(1,1,n,st,dr,a+(st-1)*b,-b); } } cin>>q; while(q--) { int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; assert(y1==1&&y2==1); cout<<query(1,1,n,x1,x2)<<'\n'; } return 0; } v.resize(n+2); for(int i=0;i<=n+1;i++) v[i].resize(m+2); for(int z=1;z<=k;z++) { int x,y,a,b; cin>>x>>y>>a>>b; int nr=a; int x1=x,y1=y,x2=x,y2=y; int cnt=0; while(nr>0&&cnt<=max(n,m)) { add(x1,y1,x2,y2,b); nr-=b; cnt++; x1--; x2++; y1--; y2++; if(x1<=0&&y1<=0&&x2>n&&y2>m) break; } //cout<<v[1][1]<<' '; x1++; x2--; y1++; y2--; add(x1,y1,x2,y2,a); add(x1,y1,x2,y2,-cnt*b); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { v[i][j]=v[i][j]+v[i-1][j]+v[i][j-1]-v[i-1][j-1]; //cout<<s[i][j]<<' '; } //assert(nradds<=k*max(n,m)); cin>>q; while(q--) { int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; ll suma=getsum(x1,y1,x2,y2); ll cells=(y2-y1+1)*(x2-x1+1); ll rez=round(ld(suma)/ld(cells)); cout<<rez<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...