Submission #829556

#	Time	Username	Problem	Language	Result	Execution time	Memory
829556		PixelCat	Rectangles (IOI19_rect)	C++17	0 / 100	129 ms	296576 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) {
        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) {
        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;
        for(auto &pv:ver[i][j]) for(auto &ph:hor[i][j]) {
            if(pv.F >= ph.F && pv.S <= ph.S) cnt++;
        }
        // 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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28