| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 365887 | kostia244 | Nuclearia (CEOI15_nuclearia) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("trapv,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int n, m, q;
vector<vector<ll>> che;
vector<ll> rur, rul;
void init() {
che.resize(n, vector<ll>(m));
rur.resize(m);
rul.resize(m);
}
void add_radius(int x, int y, int r, ll val) {
che[max(x-r, 0)][max(y-r, 0)] += val;
if(x+r+1 < n)
che[x+r+1][max(y-r, 0)] -= val;
if(y+r+1 < m)
che[max(x-r, 0)][y+r+1] -= val;
if(x+r+1 < n && y+r+1 < m)
che[x+r+1][y+r+1] += val;
}
void add_vert(int x, int y, ll a, ll b) {
ll maxrad = a/b;
add_radius(x, y, maxrad, a - b*maxrad);
//cout << a-b*maxrad << ":((" << endl;
for(int i = 0; i < min(max(n, m), maxrad); i++) {
add_radius(x, y, i, b);
}
}
void finish() {
for(int it = 0; it < 2; it++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(i) che[i][j] += che[i-1][j];
if(j) che[i][j] += che[i][j-1];
if(i&&j) che[i][j] -= che[i-1][j-1];
}
}
/*
for(auto i : che) {
for(auto j : i) cout << j << " ";
cout << endl;
}*/
}
}
ll get_rect(int xl, int xr, int yl, int yr) {
ll sum = che[xr][yr];
--xl, --yl;
if(xl>=0) sum -= che[xl][yr];
if(yl>=0) sum -= che[xr][yl];
if(xl>=0&&yl>=0) sum += che[xl][yl];
ll area = (xr-xl)*(yr-yl);
//cout << xl << " " << xr << " " << yl << " " << yr << " " << area << endl;
ll rem = sum % area;
return (sum/area) + (rem*2 >= area);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
int rev = 0;
if(n > m) swap(n, m), rev = 1;
init();
for(int x, y, a, b; q--;) {
cin >> x >> y >> a >> b;x--, y--;
if(rev) swap(x, y);
add_vert(x, y, a, b);
}
finish();
cin >> q;
for(int xl, xr, yl, yr; q--;) {
cin >> xl >> yl >> xr >> yr;xl--,xr--,yl--,yr--;
if(rev) swap(xl, yl);
if(rev) swap(xr, yr);
//cout << xl << " " << xr << " " << yl << " " << yr << " QUERY:" << endl;
cout << get_rect(xl, xr, yl, yr) << '\n';
}
}