제출 #540215

#제출 시각아이디문제언어결과실행 시간메모리
540215alextodoranNuclearia (CEOI15_nuclearia)C++17
6 / 100
837 ms1048576 KiB
/** ____ ____ ____ ____ ____ ||a |||t |||o |||d |||o || ||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\| **/ #include <bits/stdc++.h> using namespace std; typedef long long ll; vector <vector <ll>> mat; vector <vector <ll>> UL; vector <vector <ll>> UR; vector <vector <ll>> DL; vector <vector <ll>> DR; vector <vector <ll>> U; vector <vector <ll>> D; vector <vector <ll>> L; vector <vector <ll>> R; int N, M; void addUL (int x, int y, int len, int val) { mat[1][1] += (ll) val * max(0, len - max(x, y)); DR[x][y] += val; if (x - len + 1 >= 1 && y - len + 1 >= 1) { DR[x - len][y - len] -= val; } else { int mn = min(x, y) - 1; x -= mn; y -= mn; DR[x - 1][y - 1] -= val; len -= mn; if (y == 1) { D[x - 1][y] += val; if (x - len >= 1) { D[x - len][y] -= val; } } else if (x == 1) { R[x][y - 1] += val; if (y - len >= 1) { R[x][y - len] -= val; } } } } void addUR (int x, int y, int len, int val) { DL[x][y] += val; if (x - len + 1 >= 1 && y + len - 1 <= M) { DL[x - len][y - len] -= val; } else { int mn = min(x, M - y + 1) - 1; x -= mn; y += mn; DL[x - 1][y + 1] -= val; len -= mn; if (x == 1) { L[x][y + 1] += val; if (y + len <= M) { L[x][y + len] -= val; } } } } void addDL (int x, int y, int len, int val) { UR[x][y] += val; if (x + len - 1 <= N && y - len + 1 >= 1) { UR[x + len][y - len] -= val; } else { int mn = min(N - x + 1, y) - 1; x += mn; y -= mn; UR[x + 1][y - 1] -= val; len -= mn; if (y == 1) { U[x + 1][y] += val; if (x + len <= N) { U[x + len][y] -= val; } } } } void addDR (int x, int y, int len, int val) { UL[x][y] += val; if (x + len <= N && y + len <= M) { UL[x + len][y + len] -= val; } } void add (int x, int y, int len, int val) { int x1 = x - len + 1, y1 = y - len + 1; int x2 = x + len - 1, y2 = y + len - 1; x1 = max(1, x1); y1 = max(1, y1); x2 = min(N, x2); y2 = min(M, y2); mat[x1][y1] += val; mat[x1][y2 + 1] -= val; mat[x2 + 1][y1] -= val; mat[x2 + 1][y2 + 1] += val; } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> M; mat = vector <vector <ll>> (N + 2, vector <ll> (M + 2, 0)); UL = mat; UR = mat; DL = mat; DR = mat; U = mat; D = mat; L = mat; R = mat; int K; cin >> K; while (K--) { int x, y, a, b; cin >> x >> y >> a >> b; int len = a / b; addUL(x, y, len, +b); addUR(x, y + 1, len, -b); addDL(x + 1, y, len, -b); addDR(x + 1, y + 1, len, +b); add(x, y, len + 1, a % b); } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { UL[i][j] += UL[i - 1][j - 1]; UR[i][j] += UR[i - 1][j + 1]; U[i][j] += U[i - 1][j]; L[i][j] += L[i][j - 1]; } } for (int i = N; i >= 1; i--) { for (int j = M; j >= 1; j--) { DL[i][j] += DL[i + 1][j - 1]; DR[i][j] += DR[i + 1][j + 1]; D[i][j] += D[i + 1][j]; R[i][j] += R[i][j + 1]; } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { mat[i][j] += UL[i][j]; mat[i][j] += UR[i][j]; mat[i][j] += DL[i][j]; mat[i][j] += DR[i][j]; mat[i][j] += U[i][j]; mat[i][j] += D[i][j]; mat[i][j] += L[i][j]; mat[i][j] += R[i][j]; mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1]; } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1]; } } int Q; cin >> Q; while (Q--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; ll sum = mat[x2][y2] - mat[x1 - 1][y2] - mat[x2][y1 - 1] + mat[x1 - 1][y1 - 1]; ll area = (ll) (x2 - x1 + 1) * (y2 - y1 + 1); ll answer = sum / area; if (sum % area >= (area + 1) / 2 && area != 1) { answer++; } cout << answer << "\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...