제출 #792771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792771		_martynas	Rectangles (IOI19_rect)	C++14	100 / 100	3251 ms	881364 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<pii>> good_pairs(vector<int> row) {
    vector<vector<pii>> 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, 1});
            st.pop();
        }
        if(!st.empty()) {
            P[i].PB({st.top().S, 1});
            if(st.top().F == row[i]) st.pop();
        }
        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;
    }
};


ll count_rectangles(vector<vector<int>> A) {
    int n = A.size(), m = A[0].size();
    vector<vector<vector<pii>>> 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]);
        for(int j = 0; j < m; j++) {
            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(),
                                          pii{rows[i][j][k].F, 2505}, greater<pii>());
                    if(it != rows[i-1][j].end() && it->F == rows[i][j][k].F) {
                        rows[i][j][k].S += rows[i-1][j][distance(rows[i-1][j].begin(), it)].S;
                    }
                }
            }
            rows[i][j].shrink_to_fit();
        }
    }
    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);
        for(int j = 0; j < n; j++) {
            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(),
                                          pii{cols[i][j][k].F, 2505}, greater<pii>());
                    if(it != cols[i-1][j].end() && it->F == cols[i][j][k].F) {
                        cols[i][j][k].S += cols[i-1][j][distance(cols[i-1][j].begin(), it)].S;
                    }
                }
            }
            cols[i][j].shrink_to_fit();
        }
    }
    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[i-1][j][k].S, rows[i-1][j][k].F});
            }
            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].F;
                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[j-1][i][k].S;
                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].F, -1);
            }
        }
    }
	return ans;
}

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

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

• 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