Submission #274158

#TimeUsernameProblemLanguageResultExecution timeMemory
274158ne4eHbKaRectangles (IOI19_rect)C++17
72 / 100
5121 ms540904 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define ft first #define sd second #define _ <<' '<< //void* MEM = malloc(400 << 20); // //void* operator new(const size_t f) { // void* res = MEM; // MEM += f; // return res; //} // //void operator delete(void*) {} //#pragma GCC optimize("Ofast,O3") namespace S { //#include <ext/pb_ds/assoc_container.hpp> //typedef __gnu_pbds::cc_hash_table<int, int> ht; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vv; typedef pair<int, int> pii; const int N = 2505; int n, m; list<int> l[N][N], u[N][N]; int p[N], length[N], la[N]; unordered_map<int, int> fl[N]; vector<bool> mk; int c[5 * N], cn, xn, yn; pii x[N], y[N]; int f[N * 5], fmax; void finit(int n) { fmax = n; memset(f, 0, n + 1 << 2); } void fadd(int i) { for(i = fmax - i; i <= fmax; i += i & -i) f[i]++; } int fget(int i) { int v{}; for(i = fmax - i; i; i -= i & -i) v += f[i]; return v; } int get(unordered_map<int, int> &a, int b) { const auto f = a.find(b); if(f == a.end()) return 0; return f->sd; } ll solve() { ll ans = 0; unordered_map<int, int> cl, fu, cu; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { swap(cl, fl[j]); for(const int &t : l[i][j]) fl[j][t] = get(cl, t) + 1; cl.clear(); swap(cu, fu); for(const int &t : u[i][j]) fu[t] = get(cu, t) + 1; cu.clear(); const auto &a = fl[j], &b = fu; if(a.size() * b.size() < 5) { for(const auto &i : a) for(const auto &j : b) ans += i.ft <= j.sd && j.ft <= i.sd; continue; } cn = 0; for(const auto &i : a) { c[cn++] = i.ft; c[cn++] = i.sd; } for(const auto &i : b) { c[cn++] = i.ft; c[cn++] = i.sd; } sort(c, c + cn); cn = unique(c, c + cn) - c; xn = yn = 0; finit(cn); auto find = [&] (const int &z) {return lower_bound(c, c + cn, z) - c;}; for(const auto &i : a) x[xn++] = {find(i.sd), find(i.ft)}; for(const auto &i : b) y[yn++] = {find(i.ft), find(i.sd)}; sort(x, x + xn); sort(y, y + yn); int it = 0; for(int i = 0; i < xn; ++i) { for(; it < yn && y[it].ft <= x[i].ft; ++it) fadd(y[it].sd); ans += fget(x[i].sd); } } fu.clear(); } return ans; } int last(int i) { return la[i] == i ? i : la[i] = last(la[i]); } void unite(int i, int j) { i = last(i), j = last(j); length[j] += length[i]; la[i] = j; } } S::ll count_rectangles(S::vv a) { using namespace S; n = a.size(); m = a[0].size(); for(int i = 0; i < n; ++i) { iota(p, p + m, 0); iota(la, la + m, 0); mk.assign(m, false); sort(p, p + m, [&] (const int &fi, const int &se) {return a[i][fi] < a[i][se];}); for(int t = 0; t < m; ) { int v = a[i][p[t]]; list<int> f; for(; t < m && a[i][p[t]] == v; ++t) { int j = p[t]; mk[j] = true; length[j] = 1; f.push_back(j); if(j + 1 < m && mk[j + 1]) unite(j, j + 1); if(j && mk[j - 1]) unite(j - 1, j); } for(int i : f) mk[last(i)] = false; for(int j : f) { j = last(j); if(mk[j]) continue; mk[j] = true; if(i == 0 || i == n - 1) continue; if(j == m - 1 || length[j] == j + 1) continue; l[i][j].push_back(length[j]); } } } for(int j = 0; j < m; ++j) { iota(p, p + n, 0); iota(la, la + n, 0); mk.assign(n, false); sort(p, p + n, [&] (const int &fi, const int &se) {return a[fi][j] < a[se][j];}); for(int t = 0; t < n; ) { int v = a[p[t]][j]; list<int> f; for(; t < n && a[p[t]][j] == v; ++t) { int i = p[t]; mk[i] = true; length[i] = 1; f.push_back(i); if(i + 1 < n && mk[i + 1]) unite(i, i + 1); if(i && mk[i - 1]) unite(i - 1, i); } for(int j : f) mk[last(j)] = false; for(int i : f) { i = last(i); if(mk[i]) continue; mk[i] = true; if(j == 0 || j == m - 1) continue; if(i == n - 1 || length[i] == i + 1) continue; u[i][j].push_back(length[i]); } } } return solve(); } #undef ft #undef sd #undef _

Compilation message (stderr)

rect.cpp: In function 'void S::finit(int)':
rect.cpp:42:46: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   42 | void finit(int n) { fmax = n; memset(f, 0, n + 1 << 2); }
      |                                            ~~^~~
#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...