Submission #565238

#TimeUsernameProblemLanguageResultExecution timeMemory
565238piOOENuclearia (CEOI15_nuclearia)C++17
25 / 100
1151 ms826944 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) begin(x), end(x) #define sz(x) ((int)size(x)) #define trace(x) cout << #x << ": " << (x) << endl; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; vector<int> x(k + 1), y(k + 1); vector<ll> a(k + 1), b(k + 1); for (int i = 1; i <= k; ++i) { cin >> x[i] >> y[i] >> a[i] >> b[i]; } vector<vector<ll>> v(n + 2, vector<ll>(m + 2)), pref(n + 2, vector<ll>(m + 2)), aa(n + 2, vector<ll>(m + 2)), bb(n + 2, vector<ll>(m + 2)), cc(n + 2, vector<ll>(m + 2)), addi(n + 2, vector<ll>(m + 2)); auto addR = [&](int i, int j, int h, ll x) { bool ok1 = 0 <= i && i <= n + 1; bool ok2 = 0 <= j && j <= m + 1; if (!ok1) { while (1) { } } if (!ok2) { while (1) { } } bb[i][j] += x; int ni = min(n + 1, i + h); int nj = min(m + 1, j + h); bb[ni][nj] -= x; }; auto addL = [&](int i, int j, int h, ll x) { bool ok1 = 0 <= i && i <= n + 1; bool ok2 = 0 <= j && j <= m + 1; if (!ok1) { while (1) { } } if (!ok2) { while (1) { } } cc[i][j] += x; int ni = min(n + 1, i + h); int nj = max(0, j - h); cc[ni][nj] -= x; }; for (int i = 1; i <= k; ++i) { int h = (a[i] - 1) / b[i]; ll val = a[i] - h * b[i]; if (x[i] < h) { while (1) {} } if (y[i] < h) { while (1) {} } if (x[i] + h > n) { while (1) { } } if (y[i] + h > m) { while (1) { } } aa[x[i] - h][y[i] - h] += val; aa[x[i] + h + 1][y[i] + h + 1] += val; aa[x[i] - h][y[i] + h + 1] -= val; aa[x[i] + h + 1][y[i] - h] -= val; if (h) { addR(x[i] - h + 1, y[i] - h + 1, h, b[i]); addR(x[i] + 1, y[i] + 1, h, b[i]); addL(x[i] - h + 1, y[i] + h, h, -b[i]); addL(x[i] + 1, y[i], h, -b[i]); } } // trace("bb") for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { bb[i][j] = bb[i][j] + bb[i - 1][j - 1]; // cout << bb[i][j] << " "; } // cout << endl; } // trace("cc") for (int j = m; j > 0; --j) { for (int i = 1; i <= n; ++i) { cc[i][j] += cc[i - 1][j + 1]; } } // for (int i = 1; i <= n; ++i) { // for (int j = 1; j <= m; ++j) { // cout << cc[i][j] << " "; // } // cout << endl; // } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { v[i][j] += bb[i][j] + cc[i][j] + aa[i][j]; v[i][j] += v[i - 1][j]; v[i][j] += v[i][j - 1]; v[i][j] -= v[i - 1][j - 1]; // cout << v[i][j] << " "; } // cout << endl; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { pref[i][j] = v[i][j]; pref[i][j] += pref[i - 1][j]; pref[i][j] += pref[i][j - 1]; pref[i][j] -= pref[i - 1][j - 1]; } } auto get = [&pref](int x1, int y1, int x2, int y2) { ll ans = pref[x2][y2]; if (x1) ans -= pref[x1 - 1][y2]; if (y1) ans -= pref[x2][y1 - 1]; if (x1 && y1) ans += pref[x1 - 1][y1 - 1]; return ans; }; int q; cin >> q; for (int i = 1; i <= q; ++i) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; ll sum = get(x1, y1, x2, y2); // trace(sum) ll S = (x2 - x1 + 1) * (ll) (y2 - y1 + 1); assert(S); cout << (sum * 2 / S + 1) / 2 << '\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...