Submission #461301

#TimeUsernameProblemLanguageResultExecution timeMemory
461301vanicNuclearia (CEOI15_nuclearia)C++14
55 / 100
1094 ms178752 KiB
#include <iostream> #include <cmath> #include <cstdio> #include <algorithm> #include <cassert> #include <vector> using namespace std; typedef long long ll; const int maxn=2500000; ll range[maxn*2]; ll najl[maxn*2]; ll pref[maxn+1]; void precompute(){ for(int i=maxn; i<maxn*2; i++){ range[i]=1; najl[i]=i-maxn; } for(int i=maxn-1; i>0; i--){ range[i]=range[i*2]*2; najl[i]=najl[i*2]; } } struct tournament{ pair < ll, ll > prop[maxn*2]; void propagate(int &x){ if(!prop[x].first && !prop[x].second){ return; } if(x<maxn){ prop[x*2].first+=prop[x].first; prop[x*2].second+=prop[x].second; prop[x*2+1].first+=prop[x].first+prop[x].second*(range[x]/2); prop[x*2+1].second+=prop[x].second; } } void update2(int l, int d, pair < ll, ll > val){ ll L=l; d++; int x; ll val1; for(l+=maxn, d+=maxn; l<d; l>>=1, d>>=1){ if(l&1){ x=l++; val1=val.first+val.second*(najl[x]-L); prop[x].first+=val1; prop[x].second+=val.second; } if(d&1){ x=--d; val1=val.first+val.second*(najl[x]-L); prop[x].first+=val1; prop[x].second+=val.second; } } } void resi(){ for(int i=1; i<maxn*2; i++){ propagate(i); } } }; tournament T; /* struct tournament1{ int pot; vector < tournament > t; tournament1(int sz1, int sz2){ pot=sz1; tournament T(sz2); for(int i=0; i<pot*2; i++){ t.push_back(T); } } void update(int l, int d, int l2, int d2, pair < ll, ll > val){ d++; for(l+=pot, d+=pot; l<d; l>>=1, d>>=1){ if(l&1){ t[l++].update2(l2, d2, val); } if(d&1){ } } } }; */ int h, w; vector < vector < ll > > l1; vector < vector < ll > > pref1; vector < ll > vi; void brutaj(){ vi.resize(h, 0); l1.resize(w, vi); vi.resize(h+1, 0); pref1.resize(w+1, vi); int n; scanf("%d", &n); ll a, b, c, d; for(int i=0; i<n; i++){ scanf("%lld%lld%lld%lld", &a, &b, &c, &d); a--; b--; for(int j=0; j<w; j++){ for(int k=0; k<h; k++){ l1[j][k]+=max(0ll, c-d*max(abs(j-a), abs(k-b))); } } } for(int i=0; i<w; i++){ for(int j=0; j<h; j++){ pref1[i+1][j+1]=pref1[i+1][j]+pref1[i][j+1]-pref1[i][j]+l1[i][j]; } } int q; scanf("%d", &q); ll sum; for(int i=0; i<q; i++){ scanf("%lld%lld%lld%lld", &a, &b, &c, &d); sum=0; sum=pref1[c][d]-pref1[c][b-1]-pref1[a-1][d]+pref1[a-1][b-1]; printf("%lld\n", (ll)round((double)sum/((c-a+1)*(d-b+1)))); } } int main(){ precompute(); scanf("%d%d", &w, &h); bool p=0; if(h!=1){ brutaj(); return 0; } if(h>w){ swap(h, w); } int n, q; scanf("%d", &n); int a, b, c, d; int kol; int l, r; pair < ll, ll > val; for(int i=0; i<n; i++){ scanf("%d%d%d%d", &a, &b, &c, &d); a--; b--; if(!p){ swap(a, b); } kol=c/d; l=b-kol; r=b; if(l>-1){ val={c%d, d}; } else{ val={c%d-l*d, d}; l=0; } // cout << "upd " << val.first << ' ' << val.second << endl; T.update2(l, r, val); l=b+1; r=b+kol; r=min(r, w-1); val={c-d, -d}; if(l<=r){ T.update2(l, r, val); } } T.resi(); for(int i=0; i<w; i++){ pref[i+1]=pref[i]+T.prop[i+maxn].first; } /* for(int i=0; i<w; i++){ cout << T.query(i, i) << ' '; } cout << endl;*/ scanf("%d", &q); ll sol, dij, res; for(int i=0; i<q; i++){ scanf("%d%d%d%d", &a, &b, &c, &d); if(!p){ swap(a, b); swap(c, d); } sol=pref[d]-pref[b-1]; dij=d-b+1; res=sol/dij; if(sol%dij>=(dij+1)/2){ res++; } printf("%lld\n", res); // printf("%lld\n", (ll)T.query(0, pot-1, 1, b, d)); } return 0; }

Compilation message (stderr)

nuclearia.cpp: In function 'void brutaj()':
nuclearia.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |  scanf("%d%d", &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~
nuclearia.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   scanf("%d%d%d%d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
nuclearia.cpp:193:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |   scanf("%d%d%d%d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...