Submission #1106524

#TimeUsernameProblemLanguageResultExecution timeMemory
1106524OctagonsMosaic (IOI24_mosaic)C++17
12 / 100
1073 ms32736 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5+2, lim = 3; int n, q, a[lim][N], b[N][lim], ar[220][220]; vector<int> v, v2; ll geta(int rw, int l, int r) { return a[rw][r] - (l ? a[rw][l-1] : 0); } ll getb(int col, int l, int r) { l = max(l, lim-1); if (l > r)return 0; return b[r][col] - b[l-1][col]; } ll get(int x, int y) { if (x < 0 || y < 0)return 0; //cout << x << " " << y << " hi\n"; ll ret = 0; for (int i = 0; i+1 < lim && i <= x; i++) { ret += geta(i, 0, y); //cout<<i<<" "<<y<<" "<<geta(i, 0, y)<<"\n"; } for (int i = 0; i+1 < lim && i <= y; i++) { ret += getb(i, 0, x); //cout<<getb(i, 0, x)<<"\n"; } //cout << ret << "\n"; if (x+1 < lim || y+1 < lim)return ret; x -= (lim - 1), y -= (lim - 1); for (auto &i : v) { //cout<<i<<" "; ret += max(0ll, min(x+1ll, y-i+1ll)); } //cout<<"\n\n"; for (auto &i : v2) { //cout<<i<<" "; ret += max(0ll, min(x-i+1ll, y+1ll)); } //cout<<"\n\n"; //cout << ret << " ezo\n"; return ret; } vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) { q = L.size(); n = X.size(); v.clear(); v2.clear(); vector<long long> ret(q); for (int i = 0; i < n; i++) { a[0][i] = X[i]; b[i][0] = Y[i]; if (i < lim) { b[0][i] = X[i]; a[i][0] = Y[i]; } ar[0][i] = X[i]; ar[i][0] = Y[i]; } for (int i = 1; i < lim; i++) { for (int j = 1; j < n; j++) { a[i][j] = (a[i-1][j] || a[i][j-1] ? 0 : 1); } } for (int i = 0; i < lim; i++) { for (int j = 1; j < n; j++) { if (i == lim-1) { continue; } a[i][j] += a[i][j-1]; } } for (int i = 1; i < n; i++) { for (int j = 1; j < lim; j++) { b[i][j] = (b[i-1][j] || b[i][j-1] ? 0 : 1); } } for (int i = 1; i < n; i++) { for (int j = 0; j < lim; j++) { if (j == lim-1) { continue; } b[i][j] += b[i-1][j]; } } for (int i = lim-1; i < n; i++) { if (a[lim-1][i]) { v.push_back(i - (lim - 1)); } } for (int j = lim; j < n; j++) { if (b[j][lim-1]) { v2.push_back(j - (lim - 1)); } } for (int i = 0; i < q; i++) { int x = T[i], y = L[i]; int x2 = B[i], y2 = R[i]; ret[i] = get(x2, y2) - get(x-1, y2) - get(x2, y-1) + get(x-1, y-1); } for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { ar[i][j] = (ar[i-1][j] || ar[i][j-1] ? 0 : 1); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { //cout << ar[i][j] << " \n"[(j+1 == n)]; } } for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { ar[i][j] += ar[i][j-1]; } } for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { ar[i][j] += ar[i-1][j]; } } for (int i = 0; i < q; i++) { int x = T[i], y = L[i]; int x2 = B[i], y2 = R[i]; int xx = ar[x2][y2] - (x > 0 ? ar[x-1][y2] : 0) - (y > 0 ? ar[x2][y-1] : 0) + (x > 0 && y > 0 ? ar[x-1][y-1] : 0); assert((x > 0 && y > 0 ? ar[x-1][y-1] : 0) == get(x-1, y-1)); assert(ar[x2][y2] == get(x2, y2)); assert((x > 0 ? ar[x-1][y2] : 0) == get(x-1, y2)); assert((y > 0 ? ar[x2][y-1] : 0) == get(x2, y-1)); ret[i] = xx; } return ret; }
#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...