제출 #792644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792644		_martynas	Rectangles (IOI19_rect)	C++14	0 / 100	6 ms	4052 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

using ll = long long;
using pii = pair<int, int>;

vector<vector<int>> good_pairs(vector<int> row) {
    vector<vector<int>> P(row.size());
    stack<pii> st;
    for(int i = 0; i < (int)row.size(); i++) {
        while(!st.empty() && st.top().F <= row[i]) {
            P[i].PB(st.top().S);
            st.pop();
        }
        if(!st.empty()) P[i].PB(st.top().S);
        st.push({row[i], i});
    }
    return P;
}

struct BIT {
    static const int mxn = 2505;
    int val[mxn];
    // 0-based input
    void add(int i, int x) {
        i++;
        while(i < mxn) {
            val[i] += x;
            i += i&(-i);
        }
    }
    int get(int i) {
        i++;
        int sum = 0;
        while(i) {
            sum += val[i];
            i -= i&(-i);
        }
        return sum;
    }
};

void test() {
    auto result = good_pairs(vector<int>{4, 5, 2, 1, 3, 4});
    auto expected = vector<vector<int>>{
        vector<int>{},
        vector<int>{0},
        vector<int>{1},
        vector<int>{2},
        vector<int>{3, 2, 1},
        vector<int>{4, 1},
    };
    assert(result == expected);
}

ll count_rectangles(vector<vector<int>> A) {
    test();
    int n = A.size(), m = A[0].size();
    vector<vector<vector<int>>> rows(n), cols(m);
    vector<vector<vector<int>>> rows_len(n), cols_len(m);
    for(int i = 0; i < n; i++) {
        rows[i] = good_pairs(A[i]);
        rows_len[i] = vector<vector<int>>(m);
        for(int j = 0; j < m; j++) {
            rows_len[i][j] = vector<int>(rows[i][j].size(), 1);
            if(i) {
                for(int k = 0; k < rows[i][j].size(); k++) {
                    auto it = lower_bound(rows[i-1][j].begin(), rows[i-1][j].end(), rows[i][j][k], greater<int>());
                    if(it != rows[i-1][j].end() && *it == rows[i][j][k]) {
                        rows_len[i][j][k] += rows_len[i-1][j][distance(rows[i-1][j].begin(), it)];
                    }
                }
            }
        }
    }
    for(int i = 0; i < m; i++) {
        vector<int> col;
        for(int j = 0; j < n; j++) col.PB(A[j][i]);
        cols[i] = good_pairs(col);
        cols_len[i] = vector<vector<int>>(n);
        for(int j = 0; j < n; j++) {
            cols_len[i][j] = vector<int>(cols[i][j].size(), 1);
            if(i) {
                for(int k = 0; k < cols[i][j].size(); k++) {
                    auto it = lower_bound(cols[i-1][j].begin(), cols[i-1][j].end(), cols[i][j][k], greater<int>());
                    if(it != cols[i-1][j].end() && *it == cols[i][j][k]) {
                        cols_len[i][j][k] += cols_len[i-1][j][distance(cols[i-1][j].begin(), it)];
                    }
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i < n; i++) {
        BIT bit;
        // look at rows (i-1, j) and cols of (i, j-1)
        for(int j = 1; j < m; j++) {
            assert(bit.get(m) == 0);
            vector<pii> rows_sort_len;
            for(int k = 1; k < rows[i-1][j].size(); k++) {
                rows_sort_len.PB({rows_len[i-1][j][k], rows[i-1][j][k]});
            }
            sort(rows_sort_len.begin(), rows_sort_len.end());
            int added = 0;
            for(int k = cols[j-1][i].size()-1; k >= 0; k--) {
                int a = cols[j-1][i][k];
                while(!rows_sort_len.empty() && rows_sort_len.back().F >= i-a-1) {
                    bit.add(rows_sort_len.back().S, 1);
                    rows_sort_len.pop_back();
                    added++;
                }
                int b = cols_len[j-1][i][k];
                if(i-a > 1) {
                    int cnt = added;
                    if(j-2-b >= 0) cnt -= bit.get(j-2-b);
                    ans += cnt;
                }
            }
            for(int k = 1; k < rows[i-1][j].size(); k++) {
                bit.add(rows[i-1][j][k], -1);
            }
        }
    }
	return ans;
}

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

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:73:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 for(int k = 0; k < rows[i][j].size(); k++) {
      |                                ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:90:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 for(int k = 0; k < cols[i][j].size(); k++) {
      |                                ~~^~~~~~~~~~~~~~~~~~~
rect.cpp:106:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for(int k = 1; k < rows[i-1][j].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:125:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             for(int k = 1; k < rows[i-1][j].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~

• 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