Submission #499186

#	Time	Username	Problem	Language	Result	Execution time	Memory
499186		dxz05	Rectangles (IOI19_rect)	C++14	25 / 100	5099 ms	37220 KiB

rect

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

using namespace std;

typedef long long ll;

#define MP make_pair

long long count_rectangles(vector<vector<int>> A) {
    const int N = A.size(), M = A[0].size();

    vector<pair<int, pair<int, int>>> hor;
    vector<pair<int, pair<int, int>>> ver;
    for (int i = 0; i < N; i++){
        for (int j1 = 0; j1 < M - 2; j1++){
            int mx = A[i][j1 + 1];
            for (int j2 = j1 + 2; j2 < M; j2++){
                if (mx < min(A[i][j1], A[i][j2])){
                    hor.emplace_back(i, MP(j1, j2));
                }
                mx = max(mx, A[i][j2]);
            }
        }
    }

    for (int j = 0; j < M; j++) {
        for (int i1 = 0; i1 < N - 2; i1++) {
            int mx = A[i1 + 1][j];
            for (int i2 = i1 + 2; i2 < N; i2++) {
                if (mx < min(A[i1][j], A[i2][j])){
                    ver.emplace_back(j, MP(i1, i2));
                }
                mx = max(mx, A[i2][j]);
            }
        }
    }

    assert((int)max(hor.size(), ver.size()) <= 4 * N * M);

    map<vector<int>, int> mp;

    for (auto x : hor){
        int i = x.first, j1 = x.second.first, j2 = x.second.second;
        int ind = upper_bound(ver.begin(), ver.end(), MP(j1, MP(N, N))) - ver.begin();
        for (; ind < ver.size(); ind++){
            auto y = ver[ind];
            int j = y.first, i1 = y.second.first, i2 = y.second.second;

            if (i1 < i && i < i2 && j1 < j && j < j2){
                mp[{i1, j1, i2, j2}]++;
            }
            if (j >= j2) break;

        }
    }

    ll ans = 0;
    for (auto now : mp){
        vector<int> v = now.first;
        if ((v[2] - v[0] - 1) * (v[3] - v[1] - 1) == now.second){
            ans++;
        }
    }

	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (; ind < ver.size(); ind++){
      |                ~~~~^~~~~~~~~~~~

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