Submission #1217089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217089		Gabp	Rectangles (IOI19_rect)	C++20	59 / 100	5136 ms	791296 KiB

rect

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

const int N = 2500 + 5;
const int MX = 7e6 + 5;

struct SegTree {
    vector<int> st;

    SegTree(int n) {
        st.assign(4 * n, 0);
    }

    void update(int v, int tl, int tr, int idx, int add) {
        if (tl == tr) {
            st[v] += add;
            return;
        }

        int mid = tl + (tr - tl) / 2;
        if (idx <= mid) update(2 * v, tl, mid, idx, add);
        else update(2 * v + 1, mid + 1, tr, idx, add);
        st[v] = st[2 * v] + st[2 * v + 1];
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (tl == l && tr == r) return st[v];

        int mid = tl + (tr - tl) / 2;
        return query(2 * v, tl, mid, l, min(mid, r)) + query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r);
    }
};

vector<pair<int,int>> sorted[MX];
set<int> col[N];
vector<int> row_order[N];
vector<int> col_has[N][N];
bool has[N][N];
vector<pair<int,int>> dp_row[N];
vector<int> row_has[N];

long long int count_rectangles(vector<vector<int>> a) {
    int n = a.size(), m = a[0].size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) sorted[a[i][j]].push_back({i, j});
    }

    for (int i = 0; i < N; i++) {
        col[i].insert(-1);
        col[i].insert(n);
    }
    for (int i = MX - 1; i >= 0; i--) {
        for (auto [x, y]: sorted[i]) {
            row_order[x].push_back(y);
            col[y].insert(x);
        }

        for (auto [x, y]: sorted[i]) {
            auto it = col[y].find(x);
            
            it--;
            if (*it != -1 && *it < x - 1) {
                int l = (*it) + 1;
                int r = x - 1;
                if (col_has[l][y].empty() || col_has[l][y].back() > r) col_has[l][y].push_back(r);
            }

            it++;
            it++;
            if (*it != n && *it > x + 1) {
                int l = x + 1;
                int r = (*it) - 1;
                if (col_has[l][y].empty() || col_has[l][y].back() > r) col_has[l][y].push_back(r);
            }
        }
    }

    long long int ans = 0;
    SegTree st(m);
    for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) has[i][j] = false;

    for (int i = n - 2; i > 0; i--) {
        set<int> row;
        row.insert(-1);
        row.insert(m);

        int p = 0;
        while (p < m) {
            int curr = a[i][row_order[i][p]];
            int start = p;
            while (p < m && a[i][row_order[i][p]] == curr) {
                row.insert(row_order[i][p++]);
            }

            for (int j = start; j < p; j++) {
                int y = row_order[i][j];
                auto it = row.find(y);

                it--;
                if (*it != -1 && *it < y - 1) {
                    int l = (*it) + 1;
                    int r = y - 1;
                    row_has[l].push_back(r);
                    has[l][r] = true;
                }

                it++;
                it++;
                if (*it != m && *it > y + 1) {
                    int l = y + 1;
                    int r = (*it) - 1;
                    row_has[l].push_back(r);
                    has[l][r] = true;
                }
            }
        }

        vector<pair<int,int>> dp_col;
        for (int j = m - 2; j > 0; j--) {
            vector<pair<int,int>> ndp_col;
            int p1 = 0, p2 = 0;
            while (p1 < col_has[i][j].size() || p2 < dp_col.size()) {
                if (p1 == col_has[i][j].size()) p2++;
                else if (p2 == dp_col.size()) ndp_col.emplace_back(col_has[i][j][p1++], j);
                else if (col_has[i][j][p1] > dp_col[p2].first) ndp_col.emplace_back(col_has[i][j][p1++], j);
                else if (col_has[i][j][p1] < dp_col[p2].first) p2++;
                else {
                    p1++;
                    ndp_col.push_back(dp_col[p2++]);
                }
            }
            dp_col = move(ndp_col);

            vector<pair<int,int>> ndp_row;
            for (auto [x, y]: dp_row[j]) {
                if (!has[j][y]) continue;

                has[j][y] = false;
                ndp_row.emplace_back(x, y);
            }
            for (auto x: row_has[j]) {
                if (!has[j][x]) continue;

                has[j][x] = false;
                ndp_row.emplace_back(i, x);
            }
            dp_row[j] = move(ndp_row);
            row_has[j].clear();

            int ptr = 0;
            for (auto [x, y]: dp_col) {
                while (ptr < dp_row[j].size() && dp_row[j][ptr].first >= x) {
                    st.update(1, 0, m - 1, dp_row[j][ptr++].second, 1);
                }

                ans += st.query(1, 0, m - 1, j, y);
            }
            while (--ptr >= 0) st.update(1, 0, m - 1, dp_row[j][ptr].second, -1);
        }
    }

    return ans;
}

• 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