Submission #948958

#TimeUsernameProblemLanguageResultExecution timeMemory
948958fskaricaNuclearia (CEOI15_nuclearia)C++14
30 / 100
1070 ms550444 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pii pair<ll, ll> ll n, m; ll x, y, a, b; ll sirina, x2, y2, a2; ll q, p; vector <vector<ll>> kvadrat; vector <vector<ll>> trokut; vector <vector<ll>> trokut2; vector <ll> bla; ll zbr, sol, cnt; bool granice(int x, int y) { if (1 <= x && x <= n && 1 <= y && y <= m) return true; return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; vector<vector<ll>> mat(n + 2, vector<ll>(m + 2)); vector<vector<ll>> kvadrat(n + 2, vector<ll>(m + 2)); vector<vector<ll>> trokut(n + 2, vector<ll>(m + 2)); vector<vector<ll>> trokut2(n + 2, vector<ll>(m + 2)); cin >> p; for (int i = 0; i < p; i++) { cin >> x >> y >> a >> b; x2 = x; y2 = y; a2 = a; mat[x][y] += a; sirina = 1; while (a > 0 && granice(x, 1)) { trokut[x][max(1ll, y)] += a; trokut[x][max(1ll, min(m + 1, y + sirina))] -= a; x--; y--; sirina += 2; a -= b; } x = x2; y = y2; a = a2; sirina = 1; while (a > 0 && granice(x, 1)) { trokut[x][max(1ll, y)] += a; trokut[x][max(1ll, min(m + 1, y + sirina))] -= a; x++; y--; sirina += 2; a -= b; } x = x2; y = y2; a = a2; sirina = 1; while (a > 0 && granice(1, y)) { trokut2[max(1ll, min(n + 1, x + 1))][y] += a; trokut2[max(1ll, min(n + 1, x + sirina - 1))][y] -= a; x--; y++; sirina += 2; a -= b; } x = x2; y = y2; a = a2; sirina = 1; while (a > 0 && granice(1, y)) { trokut2[max(1ll, min(n + 1, x + 1))][y] += a; trokut2[max(1ll, min(n + 1, x + sirina - 1))][y] -= a; x--; y--; sirina += 2; a -= b; } } for (int i = 1; i <= n; i++) { zbr = 0; for (int j = 1; j <= m; j++) { zbr += trokut[i][j]; mat[i][j] += zbr; } } for (int j = 1; j <= m; j++) { zbr = 0; for (int i = 1; i <= n; i++) { zbr += trokut2[i][j]; mat[i][j] += zbr; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { kvadrat[i][j] = kvadrat[i - 1][j] + kvadrat[i][j - 1] - kvadrat[i - 1][j - 1] + mat[i][j]; } } cin >> q; while (q--) { cin >> x >> y >> x2 >> y2; sol = kvadrat[x2][y2] - kvadrat[x2][y - 1] - kvadrat[x - 1][y2] + kvadrat[x - 1][y - 1]; cnt = ((x2 - x + 1) * (y2 - y + 1)); if (sol % cnt >= (cnt + 1) / 2) sol = sol / ((x2 - x + 1) * (y2 - y + 1)) + 1; else sol = sol / ((x2 - x + 1) * (y2 - y + 1)); cout << sol << "\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...