Submission #39732

#TimeUsernameProblemLanguageResultExecution timeMemory
39732farmersriceNuclearia (CEOI15_nuclearia)C++14
55 / 100
1000 ms299852 KiB
#include <bits/stdc++.h> //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") //#pragma GCC target ("avx,tune=native") //Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside. AVX is better slightly /* TASK: hidden LANG: C++11 */ using namespace std; typedef long long ll; typedef pair<int, int> pair2; typedef pair<int, pair<int, int> > pair3; typedef pair<int, pair<int, pair<int, int> > > pair4; #define MAXN 200013 #define MAXA 2500013 #define INF 1000000000000000000LL #define mp make_pair #define add push_back #define remove pop /* Why my alg TLE? because TL too strict should only be O(w * h) with arrays... */ int n; int w, h, q; int x[MAXN], y[MAXN]; ll a[MAXN], b[MAXN]; bool swapped; ll * trees[4][MAXA]; ll * metadelta[MAXA]; //ADDS OVER EACH CELL AFTER AND INCLUDING ITSELF void update(int i, int j, ll sign) { if (i < 0 || j < 0) return; //cout << "Updating " << i << ' ' << j << ' ' << sign << endl; trees[0][i + 1][j + 1] += sign; trees[1][i + 1][j + 1] += sign * (i + 1); trees[2][i + 1][j + 1] += sign * (j + 1); trees[3][i + 1][j + 1] += sign * (i + 1) * (j + 1); } void makeArray(int a) { for (int i = 1; i <= w; i++) { for (int j = 1; j <= h; j++) { trees[a][i][j] += trees[a][i - 1][j] + trees[a][i][j - 1] - trees[a][i - 1][j - 1]; //cout << "array made " << i << ' ' << j << " value " << trees[a][i][j] << endl; } } } ll getSum(int i, int j) { if (i < 0 || j < 0) return 0; ll answer = 0; answer += trees[3][i + 1][j + 1]; //cout << "Trees 3 query " << i << ' ' << j << " is " << answer << endl; answer += (i + 1) * (trees[2][w][j + 1] - trees[2][i + 1][j + 1]); answer += (j + 1) * (trees[1][i + 1][h] - trees[1][i + 1][j + 1]); answer += (i + 1) * (j + 1) * (trees[0][w][h] - trees[0][w][j + 1] - trees[0][i + 1][h] + trees[0][i + 1][j + 1]); return answer; } ll getSum(int a, int b, int c, int d) { //a, b is bottom left //c, d is top right return getSum(c, d) - getSum(a - 1, d) - getSum(c, b - 1) + getSum(a - 1, b - 1); } void updateRect(int a, int b, int c, int d, ll value) { update(c, d, value); update(a - 1, d, -value); update(c, b - 1, -value); update(a - 1, b - 1, value); } //i copy this read in part from koosaga. my own code was too slow static char _buffer[1024]; static int _currentChar = 0; static int _charsNumber = 0; static inline int _read() { if (_charsNumber < 0) { exit(1); } if (!_charsNumber || _currentChar == _charsNumber) { _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin); _currentChar = 0; } if (_charsNumber <= 0) { return -1; } return _buffer[_currentChar++]; } static inline int _readInt() { int c, x, s; c = _read(); while (c <= 32) c = _read(); x = 0; s = 1; if (c == '-') { s = -1; c = _read(); } while (c > 32) { x *= 10; x += c - '0'; c = _read(); } if (s < 0) x = -x; return x; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //scanf("%d%d", &w, &h); //scanf("%d", &n); w = _readInt(); h = _readInt(); n = _readInt(); //cout << "Wha " << endl; for (int i = 0; i < n; i++) { //scanf("%d%d%lld%lld", &x[i], &y[i], &a[i], &b[i]); x[i] = _readInt(); y[i] = _readInt(); a[i] = _readInt(); b[i] = _readInt(); x[i]--; y[i]--; } if (w > h) { swap(w, h); for (int i = 0; i < n; i++) { swap(x[i], y[i]); } swapped = true; } for (int a = 0; a < 4; a++) for (int i = 0; i <= w; i++) { trees[a][i] = new ll[h + 1]; for (int j = 0; j < h + 1; j++) { trees[a][i][j] = 0; } } for (int i = 0; i <= w; i++) { metadelta[i] = new ll[h + 1]; for (int j = 0; j < h + 1; j++) { metadelta[i][j] = 0; } } for (int i = 0; i < n; i++) { ll possible = (a[i] - 1) / b[i]; if (possible == 0) { metadelta[x[i]][y[i]] += a[i]; if (y[i] + 1 < h) { //cout << "owie " << endl; metadelta[x[i]][y[i] + 1] += - 2 * a[i]; if (y[i] + 2 < h) metadelta[x[i]][y[i] + 2] += a[i]; } continue; } int vstart = max(0, (int) (x[i] - possible)); int vend = min(w - 1, (int) (x[i] + possible)); int hstart = max(0, (int) (y[i] - possible)); int hend = min(h - 1, (int) (y[i] + possible)); for (int j = vstart; j <= vend; j++) { ll initialValue = a[i] - b[i] * max(llabs(x[i] - j), llabs(hstart - y[i])); metadelta[j][hstart] += initialValue; if (hstart + 1 < h) { metadelta[j][hstart + 1] += -initialValue; {metadelta[j][hstart + 1] += b[i];} } //find the places where the delta is subtracted in the middle ll heightDiff = llabs(x[i] - j); ll spot1 = max(hstart + 1LL, y[i] - heightDiff + 1); ll spot2 = min(hend + 1LL, y[i] + heightDiff + 1); //cout << "row " << j << " spot1, spot2 are " << spot1 << ' ' << spot2 << endl; if (spot1 >= hstart && spot1 <= hend) metadelta[j][(int) spot1] += -b[i]; if (spot2 >= hstart && spot2 <= hend + 1) metadelta[j][(int) spot2] += -b[i]; ll finalValue = a[i] - b[i] * max(llabs(x[i] - j), llabs(hend - y[i])); if (hend + 1 < h) { metadelta[j][hend + 1] += -finalValue; if (hend + 2 < h) metadelta[j][hend + 2] += finalValue; metadelta[j][hend + 1] += b[i]; } } } for (int i = 0; i < w; i++) { ll delta = 0; ll current = 0; for (int j = 0; j < h; j++) { delta += metadelta[i][j]; current += delta; //cout << current << ' '; updateRect(i, j, i, j, current); } //cout << endl; } makeArray(0); makeArray(1); makeArray(2); makeArray(3); q = _readInt();//scanf("%d", &q);//cin >> q; for (int i = 0; i < q; i++) { ll x1, y1, x2, y2; //scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);//cin >> x1 >> y1 >> x2 >> y2; x1 = _readInt(); y1 = _readInt(); x2 = _readInt(); y2 = _readInt(); x1--; y1--; x2--; y2--; if (swapped) { swap(x1, y1); swap(x2, y2); } //cout << "bounds are " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl; ll sum = getSum(x1, y1, x2, y2); ll cells = (x2 - x1 + 1) * (y2 - y1 + 1); //cout << "query " << i << " found sum " << sum << " cells " << cells << endl; ll remainder = sum % cells; if ((cells % 2 == 0 && remainder >= cells / 2) || (cells % 2 == 1 && remainder > cells / 2)) { printf("%lld\n", 1 + sum / cells);//cout << 1 + sum / cells << endl; } else { printf("%lld\n", sum / cells);//cout << sum / cells << endl; } } 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...