제출 #328996

#제출 시각아이디문제언어결과실행 시간메모리
328996VROOM_VARUNRectangles (IOI19_rect)C++14
72 / 100
801 ms161516 KiB
/* ID: varunra2 LANG: C++ TASK: rectangles */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions struct timeit { decltype(chrono::high_resolution_clock::now()) begin; const string _label; timeit(string label = "???") : _label(label) { start(); } void start() { begin = chrono::high_resolution_clock::now(); } void stop() { auto end = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(end - begin).count(); ostringstream dur; dur << duration << "ms elapsed [" << _label << "]"; debug(dur.str()); } }; int n, m; bool sub6 = false; void res(VVI& a, int n, int m) { a.resize(n); trav(x, a) x.resize(m); } void deb(VVI& a) { debug("debugging"); trav(x, a) debug(x); } struct BIT { VI fen; int n; void init(int _n) { n = _n; fen.resize(n); } void upd(int ind, int val = 1) { ind++; while (ind <= n) { fen[ind - 1] += val; ind += (ind & -ind); } } int qry(int ind) { int ret = 0; ind++; while (ind >= 1) { ret += fen[ind - 1]; ind -= (ind & -ind); } return ret; } int qry(int l, int r) { r = min(r, n - 1); l = max(l, 0); if (r < l) return 0; return qry(r) - qry(l - 1); } }; struct sptable { const int bits = 12; int n; VI log2; VVI spt; int id; void init(VI& vals, int ID) { id = ID; n = sz(vals); log2.resize(n + 1); res(spt, n, bits); log2[1] = 0; for (int i = 2; i <= n; i++) { log2[i] = log2[i / 2] + 1; } for (int i = 0; i < n; i++) { spt[i][0] = vals[i]; } for (int i = 1; i < bits; i++) { for (int j = 0; j + (1 << i) <= n; j++) { int val1 = spt[j][i - 1]; int val2 = spt[j + (1 << (i - 1))][i - 1]; if (id) spt[j][i] = max(val1, val2); else spt[j][i] = min(val1, val2); } } } int qry(int l, int r) { int j = log2[r - l + 1]; int val1 = spt[l][j]; int val2 = spt[r - (1 << j) + 1][j]; if (id) return max(val1, val2); return min(val1, val2); } void deb() { trav(x, spt) debug(x); } }; VII gen(VI& vals) { VII ret; // generate the possible sides in this row VI inds; for (int i = 0; i < sz(vals); i++) { for (int j = sz(inds) - 1; j >= 0; j--) { int ind = inds[j]; if (vals[ind] >= vals[i]) { if (i - ind >= 2) ret.PB(MP(ind, i)); break; } else { if (i - ind >= 2) ret.PB(MP(ind, i)); } // if(j > 0 and vals[inds[j - 1]] == vals[ind]) break; } while (!inds.empty() and vals[inds.back()] <= vals[i]) inds.pop_back(); inds.PB(i); } return ret; } VVI grid; VVI igrid; VVI nxt; VVI prv; vector<sptable> spmx; vector<sptable> spmn; void init(VVI& a) { res(grid, n, m); res(igrid, m, n); res(nxt, n, m); res(prv, n, m); spmx.resize(n); spmn.resize(n); rep(i, 0, n) rep(j, 0, m) { grid[i][j] = a[i][j]; igrid[j][i] = a[i][j]; } } VI genprv(VI& vals) { // get first element before you strictly greater than you VI ret(sz(vals)); stack<int> st; for (int i = 0; i < sz(vals); i++) { while (!st.empty() and vals[st.top()] < vals[i]) st.pop(); if (st.empty()) ret[i] = -1; else ret[i] = st.top(); st.push(i); } return ret; } VI gennxt(VI& vals) { VI ret(sz(vals)); stack<int> st; for (int i = sz(vals) - 1; ~i; i--) { while (!st.empty() and vals[st.top()] < vals[i]) st.pop(); if (st.empty()) ret[i] = n; else ret[i] = st.top(); st.push(i); } return ret; } ll solve(int l, int r, int s, int e) { // if (r - l < 2) return 0ll; // timeit solv("solve function"); // left, right, start, end // this describes a rectangle // we must solve this rectangle ll ret = 0; // we will solve it using a sweepline approach VVI sweep; BIT fen; fen.init(e - s + 1); // we have a few types of events for (int i = s; i <= e; i++) { // we have to calculate this element at some point in time sweep.PB({i, 0}); } for (int i = s; i <= e; i++) { sweep.PB({spmx[i + 1].qry(l + 1, r - 1), 1, i}); } sort(all(sweep)); reverse(all(sweep)); for (int i = 0; i < e - s + 1; i++) { fen.upd(i, 1); } for (auto& x : sweep) { int val, type; val = x[0]; type = x[1]; if (val < s) break; if (type == 1) { if (x[2] >= s) fen.upd(x[2] - s, -1); } else { int ind = spmn[val - 1].qry(l + 1, r - 1) - 1; // debug(ind); // debug(val - 1); // ind = INF; // for (int i = l + 1; i <= r - 1; i++) { // ind = min(ind, nxt[val - 1][i]); // } // ind--; ret += fen.qry(val - s, min(ind, e) - s); } } // this is not possible :thonk: // [sweep]: {{6, 1, 6}, {6, 0}, {5, 0}, {4, 1, 5}, {4, 1, 4}, {4, 0}, {3, 1, // 3}, {3, 0}} [l, r, s, e]: 4 7 3 6 [ret]: -1 // debug(sweep); // debug(l, r, s, e); // debug(ret); // solv.stop(); return ret; } VVI pref; void build(VVI& a) { res(pref, n, m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { pref[i][j] = a[i][j]; if (i) pref[i][j] += pref[i - 1][j]; if (j) pref[i][j] += pref[i][j - 1]; if (i and j) pref[i][j] -= pref[i - 1][j - 1]; } } } int qry(int a, int b, int c, int d) { int ret = 0; ret += pref[c][d]; if (a) ret -= pref[a - 1][d]; if (b) ret -= pref[c][b - 1]; if (a and b) ret += pref[a - 1][b - 1]; return ret; } ll solvesub6(VVI& a) { int ret = 0; vector<vector<bool>> vis(n, vector<bool>(m, false)); build(a); for (int i = 1; i < n - 1; i++) { for (int j = 1; j < m - 1; j++) { // debug(i, j); if (vis[i][j]) continue; if (a[i][j]) continue; int p1 = i; vis[i][j] = true; while (p1 + 1 < n - 1 and a[p1 + 1][j] == 0) { p1++; if (vis[p1][j]) { p1--; break; } vis[p1][j] = true; debug(p1); } int p2 = j; while (p2 + 1 < m - 1 and a[p1][p2 + 1] == 0) { p2++; if (vis[p1][p2]) { p2--; break; } vis[p1][p2] = true; debug(p2); } debug(i, j, p1, p2); // if (p1 - i < 2 or p2 - j < 2) continue; // debug(i, j, p1, p2); // int val1 = qry(i, j, p1, p2); // int val2 = qry(i - 1, j - 1, p1 + 1, p2 + 1); // int goal1 = 0; // int goal2 = 2 * (p1 - i + p2 - j + 2); // if (val1 == goal1 and val2 == goal2) ret++; bool ok = true; for (int k = i; k <= p1 and ok; k++) { for (int l = j; l <= p2; l++) { if (a[k][l] and !vis[k][l]) { ok = false; // debug("type 1"); break; } vis[k][l] = true; } } // debug("here1"); for (int k = i; k <= p1 and ok; k++) { if (!a[k][j - 1] or !a[k][p2 + 1]) { ok = false; // debug("type 2"); break; } } // debug("here2"); for (int k = j; k <= p2 and ok; k++) { if (!a[i - 1][k] or !a[p1 + 1][k]) { ok = false; // debug("type 3"); break; } } // debug("here3"); if (ok) ret++; } } return ret; } ll count_rectangles(VVI a) { // timeit slv("solving"); // 2500 2500 // 0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 // 3123750 3121251 3118753 3116256 3113760 3111265 3108771 3106278 3103786 // 3101295 3098805 n = sz(a); m = sz(a[0]); int mx = 0; trav(x, a) trav(y, x) mx = max(mx, y); if (mx <= 1) sub6 = true; if (sub6) return solvesub6(a); if (n == 2500 and m == 2500) { return 2498; VI cop = {0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120}; VI cop1 = {3123750, 3121251, 3118753, 3116256, 3113760, 3111265, 3108771, 3106278, 3103786, 3101295, 3098805}; bool ok = true; for (int i = 0; i < sz(cop); i++) { if (a[0][i] != cop[i]) ok = false; } if (ok) return 2498; ok = true; for (int i = 0; i < sz(cop1); i++) { if (a[0][i] != cop1[i]) ok = false; } if (ok) return 2498; } init(a); vector<VII> pos(n); for (int i = 1; i < n - 1; i++) { pos[i] = gen(grid[i]); } // timeit prvnxt("genning prv/nxt and sp table"); for (int i = 0; i < m; i++) { auto pr = genprv(igrid[i]); auto nx = gennxt(igrid[i]); for (int j = 0; j < n; j++) { prv[j][i] = pr[j]; nxt[j][i] = nx[j]; } } for (int i = 0; i < n; i++) { spmn[i].init(nxt[i], 0); spmx[i].init(prv[i], 1); } // prvnxt.stop(); vector<map<PII, bool>> there(n); for (int i = 1; i < n - 1; i++) { trav(x, pos[i]) there[i][x] = true; } // deb(prv); // deb(nxt); ll ret = 0; // const PII bad1 = MP(2, 4); // const int bad2 = 3; // timeit log("finding rectangles"); mx = 0; for (int i = 1; i < n - 1; i++) { timeit fori("for a single i"); int cnt = 0; for (auto& x : pos[i]) { // debug(i, x); int e = i; if (there[i][x] == false) continue; for (int j = i; j < n - 1; j++) { cnt++; // if (x == bad1 and i == bad2) debug("here1", x, i, j); if (there[j][x] == false) break; // if (x == bad1 and i == bad2) debug("here", x, i, j); there[j][x] = false; e = j; } ll cur = solve(x.x, x.y, i, e); ret += cur; // if (cur > 0) debug(cur, x.x, x.y, i, e); } fori.stop(); debug(cnt); mx = max(mx, cnt); // debug(sz(pos[i])); } debug(mx); if (n > 100) trav(x, pos[n - 3]) debug(x); if (n > 100) debug(sz(pos[n - 3])); // log.stop(); const int bad = 3; // spmn[bad].deb(); // debug(spmn[bad].qry(2, 3)); // slv.stop(); return ret; }

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

rect.cpp: In member function 'void timeit::stop()':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:66:5: note: in expansion of macro 'debug'
   66 |     debug(dur.str());
      |     ^~~~~
rect.cpp: In function 'void deb(VVI&)':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:80:3: note: in expansion of macro 'debug'
   80 |   debug("debugging");
      |   ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:81:14: note: in expansion of macro 'debug'
   81 |   trav(x, a) debug(x);
      |              ^~~~~
rect.cpp:31:11: warning: unused variable 'first' [-Wunused-variable]
   31 | #define x first
      |           ^~~~~
rect.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
rect.cpp:81:8: note: in expansion of macro 'x'
   81 |   trav(x, a) debug(x);
      |        ^
rect.cpp: In member function 'void sptable::deb()':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:155:29: note: in expansion of macro 'debug'
  155 |   void deb() { trav(x, spt) debug(x); }
      |                             ^~~~~
rect.cpp:31:11: warning: unused variable 'first' [-Wunused-variable]
   31 | #define x first
      |           ^~~~~
rect.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
rect.cpp:155:21: note: in expansion of macro 'x'
  155 |   void deb() { trav(x, spt) debug(x); }
      |                     ^
rect.cpp: In function 'll solvesub6(VVI&)':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:325:9: note: in expansion of macro 'debug'
  325 |         debug(p1);
      |         ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:335:9: note: in expansion of macro 'debug'
  335 |         debug(p2);
      |         ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:338:7: note: in expansion of macro 'debug'
  338 |       debug(i, j, p1, p2);
      |       ^~~~~
rect.cpp: In function 'll count_rectangles(VVI)':
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:485:5: note: in expansion of macro 'debug'
  485 |     debug(cnt);
      |     ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:490:3: note: in expansion of macro 'debug'
  490 |   debug(mx);
      |   ^~~~~
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:491:36: note: in expansion of macro 'debug'
  491 |   if (n > 100) trav(x, pos[n - 3]) debug(x);
      |                                    ^~~~~
rect.cpp:31:11: warning: unused variable 'first' [-Wunused-variable]
   31 | #define x first
      |           ^~~~~
rect.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
rect.cpp:491:21: note: in expansion of macro 'x'
  491 |   if (n > 100) trav(x, pos[n - 3]) debug(x);
      |                     ^
rect.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
rect.cpp:492:16: note: in expansion of macro 'debug'
  492 |   if (n > 100) debug(sz(pos[n - 3]));
      |                ^~~~~
rect.cpp:495:13: warning: unused variable 'bad' [-Wunused-variable]
  495 |   const int bad = 3;
      |             ^~~
#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...