Submission #322132

#	Time	Username	Problem	Language	Result	Execution time	Memory
322132		12tqian	Rectangles (IOI19_rect)	C++17	50 / 100	3334 ms	606572 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
 
#define eb emplace_back
#define pb push_back
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
 
 
// #ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
// #else
// #define dbg(...) 17;
// #endif
 
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
 
template<class T> struct BIT {
    vector<T> bit;
    int n;
    
    void init(int n_) {
        n = n_;
        bit.resize(n);
    }
    
    T sum(int r) {
        T ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
        return ret;
    }
    
    T sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    
    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta;
    }
};
 
struct seg { 
    short t;
    short l, r;
    short x, y;
    seg(short t_, short l_, short r_, short x_, short y_) {
        t = t_, l = l_, r = r_, x = x_, y = y_;
    }
};
 
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n = (int) a.size();
    int m = (int) a[0].size();
    vector<vector<pair<short, short>>> rows(n);
    vector<vector<pair<short, short>>> cols(m);
    for (int i = 0; i < n; i++) {
        vector<int> stk;
        for (int j = 0; j < m; j++) {
            while (sz(stk) && a[i][stk.back()] < a[i][j]) {
                if (stk.back() + 2 <= j) 
                    rows[i].emplace_back(stk.back(), j);
                stk.pop_back();
            }
            if (sz(stk) && stk.back() + 2 <= j) 
                rows[i].emplace_back(stk.back(), j);    
            stk.push_back(j);
            while (sz(stk) >= 2 && a[i][stk[sz(stk) - 1]] == a[i][stk[sz(stk) - 2]]) {
                swap(stk[sz(stk) - 1], stk[sz(stk) - 2]);
                stk.pop_back();
            }
        }
    }
    for (int j = 0; j < m; j++) {
        vector<int> stk;
        for (int i = 0; i < n; i++) {
            while (sz(stk) && a[stk.back()][j] < a[i][j]) {
                if (stk.back() + 2 <= i) 
                    cols[j].emplace_back(stk.back(), i);
                stk.pop_back();
            }
            if (sz(stk) && stk.back() + 2 <= i) 
                cols[j].emplace_back(stk.back(), i);
            stk.push_back(i);
            while (sz(stk) >= 2 && a[stk[sz(stk) - 1]][j] == a[stk[sz(stk) - 2]][j]) {
                swap(stk[sz(stk) - 1], stk[sz(stk) - 2]);
                stk.pop_back();
            }
        }
    }
    vector<vector<vector<seg>>> vert_corner(n + 5, vector<vector<seg>>(m + 5));
    vector<vector<pair<short, short>>> vert(m, vector<pair<short, short>>(m, {(short) -1, (short) -1}));
    vector<seg> tot;
    for (int i = 0; i < n; i++) {
        for (auto bar : rows[i]) {
            if (vert[bar.first][bar.second] == make_pair((short) -1, (short) -1)) {
                vert[bar.first][bar.second] = {i, i};
            } else {
                if (vert[bar.first][bar.second].second + 1 == i) {
                    vert[bar.first][bar.second].second++;
                } else {
                    int lo = vert[bar.first][bar.second].first;
                    int hi = vert[bar.first][bar.second].second;
                    for (int z = lo - 1; z <= hi + 1; z++) 
                        vert_corner[z + 1][bar.first + 1].emplace_back(1, bar.first + 1, bar.second + 1, lo, hi + 2);
                    vert[bar.first][bar.second] = {i, i};
                }
            }
        }
        if (i == n - 1) {
            for (int x = 0; x < m; x++) {
                for (int y = 0; y < m; y++) {
                    if (vert[x][y] == make_pair((short) -1, (short) -1)) continue;
                    int lo = vert[x][y].first; 
                    int hi = vert[x][y].second;
                    for (int z = lo - 1; z <= hi + 1; z ++) 
                        vert_corner[z + 1][x + 1].emplace_back(1, x + 1, y + 1, lo, hi + 2);
                }
            }
        }
    }
    rows.clear();
    vert.clear();
    vector<vector<vector<seg>>> hori_corner(n + 5, vector<vector<seg>>(m + 5));
    vector<vector<pair<short, short>>> hori(n, vector<pair<short, short>>(n, {(short) -1, (short) -1}));
    for (int j = 0; j < m; j++) {
        for (auto bar : cols[j]) {
            if (hori[bar.first][bar.second] == make_pair((short) -1, (short) -1)) {
                hori[bar.first][bar.second] = {j, j};
            } else {
                if (hori[bar.first][bar.second].second + 1 == j) {
                    hori[bar.first][bar.second].second++;
                } else {
                    int lo = hori[bar.first][bar.second].first;
                    int hi = hori[bar.first][bar.second].second;
                    for (int z = lo - 1; z <= hi + 1; z++) 
                        hori_corner[bar.first + 1][z + 1].emplace_back(0, bar.first + 1, bar.second + 1, lo, hi + 2);
                    hori[bar.first][bar.second] = {j, j};
                }
            }
        }
        if (j == m - 1) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    if (hori[x][y] == make_pair((short) -1, (short) -1)) continue;
                    int lo = hori[x][y].first; 
                    int hi = hori[x][y].second;
                    for (int z = lo - 1; z <= hi + 1; z++) 
                        hori_corner[x + 1][z + 1].emplace_back(0, x + 1, y + 1, lo, hi + 2);           
                }
            }
        }
    }   
    cols.clear();
    hori.clear();
    long long ans = 0;
    BIT<int> B;
    B.init(n + 5);
    for (int i = 0; i < n + 5; i++) {
        for (int j = 0; j < m + 5; j++) {
            vector<seg> segs;
            for (auto s : hori_corner[i][j]) {
                segs.push_back(s);
                B.add(s.r, 1);
            }
            for (auto s : vert_corner[i][j]) segs.push_back(s);
            sort(segs.begin(), segs.end(), [](seg& one, seg& two) {
                if (one.t == 0 && two.t == 0) {
                    return one.y <= two.y;
                } else if (one.t == 0 && two.t == 1) {
                    if (one.y == two.r) return false;
                    return one.y <= two.r;
                } else if (one.t == 1 && two.t == 0) {
                    if (one.r == two.y) return true;
                    return one.r <= two.y;
                } else {
                    return one.r <= two.r;
                }
            });
            for (auto s : segs) {
                if (s.t == 0) {
                    B.add(s.r, -1);
                } else {
                    ans += B.sum(0, s.y);
                }
            }
        }
    }
	return ans;
}

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