Submission #829566

#	Time	Username	Problem	Language	Result	Execution time	Memory
829566		PixelCat	Rectangles (IOI19_rect)	C++17	59 / 100	5039 ms	342648 KiB

rect

#include "rect.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 2500;

#define LO(x) ((x) & (-(x)))
struct BIT {
    int n, tot;
    int a[MAXN + 10];
    void init(int _n) {
        n = _n;
        tot = 0;
        memset(a, 0, sizeof(a));
    }
    void add(int i, int x) {
        while(i <= n) {
            a[i] += x;
            i += LO(i);
        }
        tot += x;
    }
    int ask(int i) {
        int res = 0;
        while(i) {
            res += a[i];
            i -= LO(i);
        }
        return res;
    }
    int suf(int i) {
        return tot - ask(i - 1);
    }
} bit;

vector<pii> ver[MAXN + 10][MAXN + 10];
vector<pii> hor[MAXN + 10][MAXN + 10];

long long count_rectangles(vector<vector<int32_t>> a) {
    int n = sz(a);
    int m = sz(a[0]);


    // collect 'sticks'
    vector<pii> stk;  // {index, value}

    // horizontal sticks
    For(i, 0, n - 1) {
        For(l, 0, m - 3) {
            int mx = -1;
            For(r, l + 2, m - 1) {
                mx = max(mx, (int)a[i][r - 1]);
                if(mx < min(a[i][l], a[i][r])) {
                    hor[i][r - 1].eb(i, l + 1);
                }
            }
        }
    }
    // For(i, 0, n - 1) {
    //     stk.clear();
    //     For(j, 0, m - 1) {
    //         while(sz(stk) && stk.back().S < a[i][j]) stk.pop_back();
    //         if(sz(stk) && stk.back().F + 1 <= j - 1) hor[i][j - 1].eb(i, stk.back().F + 1);
    //         stk.eb(j, a[i][j]);
    //     }
    //     stk.clear();
    //     Forr(j, m - 1, 0) {
    //         while(sz(stk) && stk.back().S <= a[i][j]) stk.pop_back();
    //         if(sz(stk) && stk.back().F - 1 >= j + 1) hor[i][stk.back().F - 1].eb(i, j + 1);
    //         stk.eb(j, a[i][j]);
    //     }
    // }

    // vertical sticks
    For(j, 0, m - 1) {
        For(u, 0, n - 3) {
            int mx = -1;
            For(d, u + 2, n - 1) {
                mx = max(mx, (int)a[d - 1][j]);
                if(mx < min(a[u][j], a[d][j])) {
                    ver[d - 1][j].eb(u + 1, j);
                }
            }
        }
    }
    // For(j, 0, m - 1) {
    //     stk.clear();
    //     For(i, 0, n - 1) {
    //         while(sz(stk) && stk.back().S < a[i][j]) stk.pop_back();
    //         if(sz(stk) && stk.back().F + 1 <= i - 1) ver[i - 1][j].eb(stk.back().F + 1, j);
    //         stk.eb(i, a[i][j]);
    //     }
    //     stk.clear();
    //     Forr(i, n - 1, 0) {
    //         while(sz(stk) && stk.back().S <= a[i][j]) stk.pop_back();
    //         if(sz(stk) && stk.back().F - 1 >= i + 1) ver[stk.back().F - 1][j].eb(i + 1, j);
    //         stk.eb(i, a[i][j]);
    //     }
    // }


    // merge sticks
    For(i, 1, n - 2) For(j, 1, m - 2) {
        map<int, int> mp;
        for(auto &p:hor[i - 1][j]) mp[p.S] = p.F;
        for(auto &p:hor[i][j]) {
            if(mp.count(p.S)) p.F = mp[p.S];
        }
        mp.clear();
        for(auto &p:ver[i][j - 1]) mp[p.F] = p.S;
        for(auto &p:ver[i][j]) {
            if(mp.count(p.F)) p.S = mp[p.F];
        }
    }

    // cerr << "horizontal:\n";
    // For(i, 0, n - 1) For(j, 0, m - 1) for(auto &k:hor[i][j]) {
    //     cerr << "[" << k.F << ", " << i << "] : ";
    //     cerr << "[" << k.S << ", " << j << "]\n";
    // }
    // cerr << "vertical:\n";
    // For(i, 0, n - 1) For(j, 0, m - 1) for(auto &k:ver[i][j]) {
    //     cerr << "[" << k.F << ", " << i << "] : ";
    //     cerr << "[" << k.S << ", " << j << "]\n";
    // }


    // count answer
    int ans = 0;
    bit.init(n);
    For(i, 1, n - 2) For(j, 1, m - 2) {
        int cnt = 0;
        vector<pair<int, pii>> v;
        for(auto &p:ver[i][j]) v.eb(0, p);
        for(auto &p:hor[i][j]) v.eb(1, p);
        sort(all(v), [&](pair<int, pii> &p1, pair<int, pii> &p2) {
            if(p1.S.S != p2.S.S) return p1.S.S < p2.S.S;
            if(p1.S.F != p2.S.F) return p1.S.F > p2.S.F;
            return p1.F < p2.F;
        });
        for(auto &it:v) {
            int ii, jj;
            tie(ii, jj) = it.S;
            ii++; jj++;
            if(it.F == 0) {
                bit.add(ii, 1);
            } else {
                cnt += bit.suf(ii);
            }
        }
        for(auto &it:v) {
            if(it.F == 0) {
                bit.add(it.S.F + 1, -1);
            }
        }
        ans += cnt;
        // cerr << i << " " << j << " " << cnt << " " << sz(v) << "\n";
    }


    return ans;
}

/*

6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

6

*/

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