Submission #274227

#	Time	Username	Problem	Language	Result	Execution time	Memory
274227		ne4eHbKa	Rectangles (IOI19_rect)	C++17	10 / 100	992 ms	384760 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define ft first
#define sd second
#define _ <<' '<<

void* MEM = malloc(800 << 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<short> l[N][N], u[N][N];
int p[N], length[N], la[N];
list<pii> fl[N], cl, fu, cu;
bool mk[N];
int c[2 * N], cn, xn, yn, rc[2 * N];
pii x[N], y[N];
int f[N], fn;

int fw[2 * N], fmax, nx[N + N], pr[N + N];
inline void finit(const int n) { fmax = n; memset(fw, 0, n + 1 << 2); }
inline void fadd(int i) { for(i = fmax - i; i <= fmax; i = nx[i]) fw[i]++; }
inline int fget(int i) { int v{}; for(i = fmax - i; i; i = pr[i]) v += fw[i]; return v; }

ll solve() {
    for(int i = 0; i < N + N; ++i) nx[i] = i + (i & -i), pr[i] = i - (i & -i);
    ll ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            swap(cl, fl[j]);
            auto it = cl.begin();
            for(const int &t : l[i][j]) {
                for(; it != cl.end() && it->ft < t; ++it);
                fl[j].push_back({t, 1 + (it != cl.end() ? it->sd : 0)});
            }
            cl.clear();
            swap(cu, fu);
            it = cu.begin();
            for(const int &t : u[i][j]) {
                for(; it != cu.end() && it->ft < t; ++it);
                fu.push_back({t, 1 + (it != cu.end() ? it->sd : 0)});
            }
            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;
            for(const auto &i : b) c[cn++] = i.sd;
            sort(c, c + cn);
            cn = unique(c, c + cn) - c;
            xn = yn = 0;
            finit(cn);
            for(int i = 0; i < cn; ++i) rc[c[i]] = i;
            for(const auto &i : a) x[xn++] = {i.sd, rc[i.ft]};
            for(const auto &i : b) y[yn++] = {i.ft, rc[i.sd]};
            sort(x, x + xn, [] (const pii &a, const pii &b) {return a.ft < b.ft;});
            for(int i = 0, it = 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);
        memset(mk, 0, m);
        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]];
            fn = 0;
            for(; t < m && a[i][p[t]] == v; ++t) {
                int j = p[t];
                mk[j] = true;
                length[j] = 1;
                f[fn++] = j;
                if(j + 1 < m && mk[j + 1]) unite(j, j + 1);
                if(j && mk[j - 1]) unite(j - 1, j);
            }
            for(int it = 0; it < fn; ++it) mk[f[it] = last(f[it])] = false;
            for(int it = 0; it < fn; ++it) {
                int j = f[it];
                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);
        memset(mk, 0, n);
        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];
            fn = 0;
            for(; t < n && a[p[t]][j] == v; ++t) {
                int i = p[t];
                mk[i] = true;
                length[i] = 1;
                f[fn++] = i;
                if(i + 1 < n && mk[i + 1]) unite(i, i + 1);
                if(i && mk[i - 1]) unite(i - 1, i);
            }
            for(int it = 0; it < fn; ++it) mk[f[it] = last(f[it])] = false;
            for(int it = 0; it < fn; ++it) {
                int i = f[it];
                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]);
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            u[i][j].sort();
            l[i][j].sort();
        }
    }
    return solve();
}

#undef ft
#undef sd
#undef _

Compilation message (stderr)

rect.cpp: In function 'void* operator new(size_t)':
rect.cpp:13:9: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
   13 |     MEM += f;
      |     ~~~~^~~~
rect.cpp: In function 'void S::finit(int)':
rect.cpp:43:60: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   43 | inline void finit(const int n) { fmax = n; memset(fw, 0, n + 1 << 2); }
      |                                                          ~~^~~

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