Submission #274096

#	Time	Username	Problem	Language	Result	Execution time	Memory
274096		ne4eHbKa	Rectangles (IOI19_rect)	C++17	72 / 100	5110 ms	540176 KiB

rect

#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() < 10) {
                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);
      |                       ~~~~~~~~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28