# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
462337 | kingfran1907 | Nuclearia (CEOI15_nuclearia) | C++14 | 1102 ms | 373184 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.
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 3e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, q;
int w, h;
bool flag = false;
vector< llint > niz[maxn], pr[maxn];
vector< llint > pref[maxn];
int main() {
scanf("%d%d", &w, &h);
if (w > h) {
swap(w, h);
flag = true;
}
for (int i = 0; i <= w; i++)
for (int j = 0; j <= h + 5; j++) {
niz[i].push_back(0);
pr[i].push_back(0);
}
scanf("%d", &n);
while (n--) {
int x, y;
llint a, b;
scanf("%d%d%lld%lld", &x, &y, &a, &b);
if (flag) swap(x, y);
for (int i = 1; i <= w; i++) {
llint aa = max(0LL, a - b * abs(i - x));
llint dist = aa / b;
int ll = max(1, y - abs(i - x));
int rr = min(h, y + abs(i - x));
int l = max(1LL, ll - dist);
int r = min((llint)h, rr + dist);
pr[i][l - 1] += aa - b * (ll - l);
pr[i][l] -= aa - b * (ll - l);
pr[i][l] += b;
pr[i][ll] -= b;
pr[i][rr] -= b;
pr[i][r] -= aa - b * (r - rr);
pr[i][r] += b;
pr[i][r + 1] += aa - b * (r - rr);
}
}
for (int i = 0; i <= w; i++) {
llint tren = pr[i][0];
for (int j = 1; j <= h; j++) {
niz[i][j] = tren + niz[i][j - 1];
tren += pr[i][j];
}
}
/*
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= h; j++) {
printf("%lld ", niz[i][j]);
}
printf("\n");
}
*/
for (int i = 0; i <= w; i++) {
for (int j = 0; j <= h + 5; j++) {
pref[i].push_back(0);
}
}
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
pref[i + 1][j + 1] = niz[i + 1][j + 1];
pref[i + 1][j + 1] += pref[i + 1][j];
}
}
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
pref[i + 1][j + 1] += pref[i][j + 1];
}
}
scanf("%d", &q);
while (q--) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x1--, y1--;
if (flag) {
swap(x1, y1);
swap(x2, y2);
}
llint sum = pref[x2][y2] - pref[x1][y2] - pref[x2][y1] + pref[x1][y1];
llint cnt = (llint)(x2 - x1) * (y2 - y1);
llint sol = sum / cnt;
llint rem = sum % cnt;
if (rem * 2 >= cnt) printf("%lld\n", sol + 1);
else printf("%lld\n", sol);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |