Submission #561900

#	Time	Username	Problem	Language	Result	Execution time	Memory
561900		hoanghq2004	Rectangles (IOI19_rect)	C++14	100 / 100	4603 ms	865564 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "rect.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2510;

int up[N][N], down[N][N], lft[N][N], rgt[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector <int> toX[N], toY[N][N];

int BIT[N];
inline void add(int i, int d) {
    ++i;
    for (; i < N; i += i & - i) BIT[i] += d;
}

inline int get(int i) {
    int ans = 0;
    ++i;
    for (; i; i -= i & - i) ans += BIT[i];
    return ans;
}

int tmp_max[N], tmp_min[N];

struct SegmentTree {
    int mini[N * 4], maxi[N * 4];
    inline void build(int id, int L, int R) {
        if (L == R) {
            mini[id] = tmp_min[L];
            maxi[id] = tmp_max[L];
            return;
        }
        int mid = L + R >> 1;
        build(id * 2, L, mid);
        build(id * 2 + 1, mid + 1, R);
        mini[id] = min(mini[id * 2], mini[id * 2 + 1]);
        maxi[id] = max(maxi[id * 2], maxi[id * 2 + 1]);
    }
    inline int get_min(int id, int L, int R, int u, int v) {
        if (u > R || L > v) return 1e9;
        if (u <= L && R <= v) return mini[id];
        int mid = L + R >> 1;
        return min(get_min(id * 2, L, mid, u, v), get_min(id * 2 + 1, mid + 1, R, u, v));
    }
    inline int get_rgt(int id, int L, int R, int i, int k) {
        if (i > R || maxi[id] <= k) return -1;
        if (L == R) return L;
        int mid = L + R >> 1;
        int ans = get_rgt(id * 2, L, mid, i, k);
        if (ans == -1) ans = get_rgt(id * 2 + 1, mid + 1, R, i, k);
        return ans;
    }
} X[N], Y[N];

long long count_rectangles(vector <vector <int>> a) {
    int n = a.size();
    int m = a[0].size();
    for (int i = 0; i < n; ++i) {
        stack <int> stk;
        for (int j = 0; j < m; ++j) {
            while (stk.size() && a[i][j] >= a[i][stk.top()]) {
                rgt[i][stk.top()] = j - 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            rgt[i][stk.top()] = m - 1;
            stk.pop();
        }
        for (int j = m - 1; j >= 0; --j) {
            while (stk.size() && a[i][j] >= a[i][stk.top()]) {
                lft[i][stk.top()] = j + 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            lft[i][stk.top()] = 0;
            stk.pop();
        }
    }
    for (int i = 0; i < m; ++i) {
        stack <int> stk;
        for (int j = 0; j < n; ++j) {
            while (stk.size() && a[j][i] >= a[stk.top()][i]) {
                down[stk.top()][i] = j - 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            down[stk.top()][i] = n - 1;
            stk.pop();
        }
        for (int j = n - 1; j >= 0; --j) {
            while (stk.size() && a[j][i] >= a[stk.top()][i]) {
                up[stk.top()][i] = j + 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            up[stk.top()][i] = 0;
            stk.pop();
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {

            if (down[i][j] < n - 1 && down[i][j] >= i + 1) {
                toY[i + 1][j].push_back(down[i][j]);
            }
            if (up[i][j] > 0 && a[i][j] != a[up[i][j] - 1][j] && up[i][j] <= i - 1) {
                toY[up[i][j]][j].push_back(i - 1);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) tmp_min[j] = down[i][j], tmp_max[j] = up[i][j];
        Y[i].build(1, 0, m - 1);
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) tmp_min[j] = rgt[j][i], tmp_max[j] = lft[j][i];
        X[i].build(1, 0, n - 1);
    }
    long long ans = 0;
    for (int u = 1; u < n - 1; ++u) {
        for (int v = 0; v < m; ++v) toX[v].clear();
        for (int v = 0; v < m; ++v) {
            if (rgt[u][v] < m - 1 && rgt[u][v] >= v + 1) {
                toX[v + 1].push_back(rgt[u][v]);
            }
            if (lft[u][v] > 0 && a[u][v] != a[u][lft[u][v] - 1] && lft[u][v] <= v - 1) {
                toX[lft[u][v]].push_back(v - 1);
            }
        }
        for (int v = 1; v < m - 1; ++v) {
            if (toX[v].empty() || toY[u][v].empty()) continue;
            vector <tuple <int, int, int> > events;
            for (auto w: toY[u][v]) { // (w, v)
                int ww = Y[w + 1].get_rgt(1, 0, m - 1, v, u);
                if (ww == -1) ww = m; --ww;
                ww = min(ww, X[v - 1].get_min(1, 0, n - 1, u, w));
                ww = min(ww, m - 2);
                add(w, 1);
                events.push_back({ww, 1, w});
            }
            for (auto w: toX[v]) { // (u, w)
                int ww = X[w + 1].get_rgt(1, 0, n - 1, u, v);
                if (ww == -1) ww = n; --ww;
                ww = min(ww, Y[u - 1].get_min(1, 0, m - 1, v, w));
                ww = min(ww, n - 2);
                events.push_back({w, 0, ww});
            }
            sort(events.begin(), events.end());
            for (auto [_, sign, k]: events) {
                if (sign == 0) ans += get(k);
                else if (sign == -1) add(k, 1);
                else add(k, -1);
            }
        }
    }
    return ans;
}

//int main() {
//    freopen("IOI19_rect.inp", "r", stdin);
////    freopen("IOI19_rect.out", "w", stdout);
//	int n, m;
//    cin >> n >> m;
//	vector<vector<int>> a(n, vector<int>(m));
//	for (int i = 0; i < n; i++)	{
//		for (int j = 0; j < m; j++) {
//            cin >> a[i][j];
//		}
//	}
//	cout << count_rectangles(a) << '\n';
//}

Compilation message (stderr)

rect.cpp: In member function 'void SegmentTree::build(int, int, int)':
rect.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = L + R >> 1;
      |                   ~~^~~
rect.cpp: In member function 'int SegmentTree::get_min(int, int, int, int, int)':
rect.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int mid = L + R >> 1;
      |                   ~~^~~
rect.cpp: In member function 'int SegmentTree::get_rgt(int, int, int, int, int)':
rect.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = L + R >> 1;
      |                   ~~^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:154:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  154 |                 if (ww == -1) ww = m; --ww;
      |                 ^~
rect.cpp:154:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  154 |                 if (ww == -1) ww = m; --ww;
      |                                       ^~
rect.cpp:162:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  162 |                 if (ww == -1) ww = n; --ww;
      |                 ^~
rect.cpp:162:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  162 |                 if (ww == -1) ww = n; --ww;
      |                                       ^~
rect.cpp:168:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  168 |             for (auto [_, sign, k]: events) {
      |                       ^

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