제출 #561875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561875		hoanghq2004	Rectangles (IOI19_rect)	C++14	0 / 100	159 ms	317280 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][N], toY[N][N];

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

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

struct SegmentTree {
    int mini[N * 4], maxi[N * 4];
    void add(int id, int L, int R, int i, int maxval, int minval) {
        if (L == R) {
            mini[id] = maxval;
            maxi[id] = minval;
            return;
        }
        int mid = L + R >> 1;
        if (i <= mid) add(id * 2, L, mid, i, maxval, minval);
        else add(id * 2 + 1, mid + 1, R, i, maxval, minval);
        mini[id] = min(mini[id * 2], mini[id * 2 + 1]);
        maxi[id] = max(maxi[id * 2], maxi[id * 2 + 1]);
    }
    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));
    }
    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 (rgt[i][j] < m - 1 && rgt[i][j] >= j + 1) {
                toX[i][j + 1].push_back(rgt[i][j]);
            }
            if (lft[i][j] > 0 && a[i][j] != a[i][lft[i][j] - 1] && lft[i][j] <= j - 1) {
                toX[i][lft[i][j]].push_back(j - 1);
            }
            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[i][up[i][j] - 1] && 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) {
            X[j].add(1, 0, n - 1, i, rgt[i][j], lft[i][j]);
            Y[i].add(1, 0, m - 1, j, down[i][j], up[i][j]);
        }
    long long ans = 0;
    for (int u = 1; u < n - 1; ++u) {
        for (int v = 1; v < m - 1; ++v) {

//    for (int u = 1; u < 2; ++u) {
//        for (int v = 2; v < 3; ++v) {
//            if (i == 0 || j == 0 || i == n - 1 || j == m - 1) assert(toX[i][j].empty() && toY[i][j].empty());
            int _ans = ans;
            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);
                cout << w << ' ' << ww << '\n';
                events.push_back({v, -1, w});
                events.push_back({ww, 1, w});
            }
            for (auto w: toX[u][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);
            }
//            if (ans != _ans) cout << u << ' ' << v << ' ' << ans - _ans << '\n';
        }
    }
    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';
//}

컴파일 시 표준 에러 (stderr) 메시지

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

• 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