Submission #274117

#TimeUsernameProblemLanguageResultExecution timeMemory
274117ne4eHbKaRectangles (IOI19_rect)C++17
72 / 100
5121 ms540184 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; #define ft first #define sd second #define _ <<' '<< //#pragma GCC optimize("Ofast,O3") namespace S { 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]; map<int, int> fl[N]; vector<bool> mk; 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(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; 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(); vi c; const auto &A = fl[j], &B = fu; if(A.size() * B.size() < 100) { for(const auto &i : A) { for(const auto &j : B) { if(i.ft <= j.sd && j.ft <= i.sd) ++ans; } } continue; } c.reserve(A.size() + B.size() << 1); for(const auto &i : A) { c.push_back(i.ft); c.push_back(i.sd); } for(const auto &i : B) { c.push_back(i.ft); c.push_back(i.sd); } sort(c.begin(), c.end()); c.resize(unique(c.begin(), c.end()) - c.begin()); finit(c.size()); list<pii> a, b; auto find = [&] (const int &z) {return lower_bound(c.begin(), c.end(), z) - c.begin();}; for(const auto &i : A) a.push_back({find(i.sd), find(i.ft)}); for(const auto &i : B) b.push_back({find(i.ft), find(i.sd)}); a.sort(); auto it = b.begin(); for(const auto t : a) { for(; it != b.end() && it->ft <= t.ft; ++it) fadd(it->sd); ans += fget(t.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:27:46: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   27 | void finit(int n) { fmax = n; memset(f, 0, n + 1 << 2); }
      |                                            ~~^~~
rect.cpp: In function 'S::ll S::solve()':
rect.cpp:61:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   61 |             c.reserve(A.size() + B.size() << 1);
      |                       ~~~~~~~~~^~~~~~~~~~
#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...