제출 #68810

#제출 시각아이디문제언어결과실행 시간메모리
68810BruteforcemanNuclearia (CEOI15_nuclearia)C++11
0 / 100
1100 ms245324 KiB
#include "bits/stdc++.h" using namespace std; vector <vector <long long>> a, tbm, tbc, rowm, rowc, colm, colc, P, Q, D; int w, h; bool inside(int x, int y) { return (0 <= x && x < w) && (0 <= y && y < h); } void addTB(int i, int j, long long x, long long d, int signx, int signy) { int len = (x / d); int doable = min(signx == -1 ? i : w - i - 1, signy == -1 ? j : h - j - 1); tbm[i][j] += -signx * d; tbc[i][j] += x + signx * d * i; if(inside(i + signx * len + signx, j + signy * len + signy)) { tbm[i + signx * len + signx][j + signy * len + signy] -= -signx * d; tbc[i + signx * len + signx][j + signy * len + signy] -= x + signx * d * i; } if(inside(i, j - signy)){ rowm[i][j - signy] += -signx * d; rowc[i][j - signy] += x + signx * d * i; if(inside(i + signx * len + signx, j - signy)) { rowm[i + signx * len + signx][j - signy] -= -signx * d; rowc[i + signx * len + signx][j - signy] -= x + signx * d * i; } } if(inside(i - signx, j)) { colm[i - signx][j] += -signy * d; colc[i - signx][j] += x + signy * d * j; if(inside(i - signx, j + signy * len + signy)) { colm[i - signx][j + signy * len + signy] -= -signy * d; colc[i - signx][j + signy * len + signy] -= x + signy * d * j; } } if(doable < len) { int ex = i + signx * len; int ey = j + signy * len; if(ex < 0) ex = 0; if(ex >= w) ex = w-1; if(ey < 0) ey = 0; if(ey >= h) ey = h-1; int fx = i + signx * doable; int fy = j + signy * doable; long long nx = x - (doable + 1) * d; if(ey == fy) { if(inside(fx + signx, fy)) { rowm[fx + signx][fy] -= -signx * d; rowc[fx + signx][fy] -= nx + signx * d * (fx + signx); } if(inside(ex + signx, ey)) { rowm[ex + signx][ey] += -signx * d; rowc[ex + signx][ey] += nx + signx * d * (fx + signx); } } else { if(inside(fx, fy + signy)) { colm[fx][fy + signy] -= -signy * d; colc[fx][fy + signy] -= nx + signy * d * (fy + signy); } if(inside(ex, ey + signy)) { colm[ex][ey + signy] += -signy * d; colc[ex][ey + signy] += nx + signy * d * (fy + signy); } } } } void reset(vector <vector<long long>> &v) { for(auto &i : v) { for(auto &j : i) { j = 0; } } } void init(vector <vector <long long>> &v) { v.resize(w); for(auto &i : v) { i.resize(h); } } int value(int x, int y) { return inside(x, y) ? a[x][y] : 0; } long long query(int x, int y, int p, int q) { long long ans = 0; ans += value(p, q); ans -= value(p, y-1); ans -= value(x-1, q); ans += value(x-1, y-1); return ans; } int main(int argc, char const *argv[]) { scanf("%d %d", &w, &h); swap(w, h); init(tbm); init(tbc); init(rowm); init(rowc); init(colm); init(colc); init(P); init(Q); init(D); init(a); int n; scanf("%d", &n); vector <pair <int, int>> u, v; for(int i = 0; i < n; i++) { int x, y, p, q; scanf("%d %d %d %d", &x, &y, &p, &q); swap(x, y); u.emplace_back(x-1, y-1); v.emplace_back(p, q); } for(int signx : {-1, 1}) { for(int signy : {-1, 1}) { reset(tbm); reset(tbc); reset(rowm); reset(rowc); reset(colm); reset(colc); reset(P); reset(Q); reset(D); for(int i = 0; i < n; i++) { addTB(u[i].first, u[i].second, v[i].first, v[i].second, signx, signy); } for(int i = w-1; i >= 0; i--) { long long sum_m = 0; long long sum_c = 0; if(signy == -1) { for(int j = h-1; j >= 0; j--) { sum_m += colm[i][j]; sum_c += colc[i][j]; Q[i][j] = sum_m * j + sum_c; } } else { for(int j = 0; j < h; j++) { sum_m += colm[i][j]; sum_c += colc[i][j]; Q[i][j] = sum_m * j + sum_c; } } } for(int j = h-1; j >= 0; j--) { long long sum_m = 0; long long sum_c = 0; if(signx == -1) { for(int i = w-1; i >= 0; i--) { sum_m += rowm[i][j]; sum_c += rowc[i][j]; P[i][j] = sum_m * i + sum_c; } } else { for(int i = 0; i < w; i++) { sum_m += rowm[i][j]; sum_c += rowc[i][j]; P[i][j] = sum_m * i + sum_c; } } } for(int j = 0; j < h; j++) { int x = signx == -1 ? w-1 : 0; int y = j; long long sum_m = 0; long long sum_c = 0; while(inside(x, y)) { sum_m += tbm[x][y]; sum_c += tbc[x][y]; D[x][y] = sum_m * x + sum_c; x += signx; y += signy; } } for(int i = 0; i < w; i++) { int x = i; int y = signy == -1 ? h-1 : 0; long long sum_m = 0; long long sum_c = 0; while(inside(x, y)) { sum_m += tbm[x][y]; sum_c += tbc[x][y]; D[x][y] = sum_m * x + sum_c; x += signx; y += signy; } } for(int i = 0; i < w; i++) { long long sum = 0; if(signy == -1) { for(int j = 0; j < h; j++) { sum += D[i][j]; sum -= P[i][j]; a[i][j] += sum; } } else { for(int j = h-1; j >= 0; j--) { sum += D[i][j]; sum -= P[i][j]; a[i][j] += sum; } } } for(int j = 0; j < h; j++) { long long sum = 0; if(signx == -1) { for(int i = 0; i < w; i++) { sum += D[i][j]; sum -= Q[i][j]; a[i][j] += sum; } } else { for(int i = w-1; i >= 0; i--) { sum += D[i][j]; sum -= Q[i][j]; a[i][j] += sum; } } } for(int i = 0; i < w; i++) { for(int j = 0; j < h; j++) { a[i][j] -= D[i][j]; } } // break; } // break; } reset(rowc); reset(rowm); reset(colc); reset(colm); for(int i = 0; i < n; i++) { int x = u[i].first; int y = u[i].second; int p = v[i].first; int q = v[i].second; rowm[min(w-1, x + (p / q))][y] += -q; rowc[min(w-1, x + (p / q))][y] += p + q * x; if(inside(x-1, y)) { rowm[x-1][y] -= -q; rowc[x-1][y] -= p + q * x; } rowm[x][y] += q; rowc[x][y] += p - q * x; if(inside(x - (p / q) - 1, y)) { rowm[x - (p / q) - 1][y] -= q; rowc[x - (p / q) - 1][y] -= p - q * x; } colm[x][min(h-1, y + (p / q))] += -q; colc[x][min(h-1, y + (p / q))] += p + q * y; if(inside(x, y-1)) { colm[x][y-1] -= -q; colc[x][y-1] -= p + q * y; } colm[x][y] += q; colc[x][y] += p - q * y; if(inside(x, y - (p / q) - 1)) { colm[x][y - (p / q) - 1] -= q; colc[x][y - (p / q) - 1] -= p - q * y; } a[x][y] += p; } for(int j = 0; j < h; j++) { long long sum_c = 0; long long sum_m = 0; for(int i = w-1; i >= 0; i--) { sum_m += rowm[i][j]; sum_c += rowc[i][j]; P[i][j] = sum_m * i + sum_c; } } for(int i = 0; i < w; i++) { long long sum_c = 0; long long sum_m = 0; for(int j = h-1; j >= 0; j--) { sum_m += colm[i][j]; sum_c += colc[i][j]; Q[i][j] = sum_m * j + sum_c; } } for(int i = 0; i < w; i++) { for(int j = 0; j < h; j++) { a[i][j] -= P[i][j] + Q[i][j]; } } for(int i = 0; i < w; i++) { for(int j = 0; j < h; j++) { a[i][j] += value(i - 1, j); a[i][j] += value(i, j - 1); a[i][j] -= value(i - 1, j - 1); } } int Q; scanf("%d", &Q); for(int i = 0; i < Q; i++) { int x, y, p, q; scanf("%d %d %d %d", &x, &y, &p, &q); swap(x, y); swap(p, q); long long sum = query(x-1, y-1, p-1, q-1); double tot = (p - x + 1) * (q - y + 1); long long res = (sum / tot) + 0.5; printf("%lld\n", res); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

nuclearia.cpp: In function 'int main(int, const char**)':
nuclearia.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &w, &h);
  ~~~~~^~~~~~~~~~~~~~~~~
nuclearia.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
nuclearia.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x, &y, &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:309:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
nuclearia.cpp:312:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x, &y, &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...