제출 #830201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830201		GusterGoose27	Rectangles (IOI19_rect)	C++17	72 / 100	5057 ms	831856 KiB

rect

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

#include "rect.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2505;
const int inf = 1e9;

typedef pair<int, int> pii;
typedef pair<pii, pii> rect;

int prv[2][MAXN][MAXN];
int nxt[2][MAXN][MAXN];
int n, m;

void make(int store[][MAXN], bool rc, bool dir, vector<vector<int>> &a, int v) {
	vector<pii> stck;
	stck.push_back(pii(inf, -1));
	int sz = (rc ? n : m);
	for (int i = (dir ? sz-1 : 0); (dir ? i >= 0 : i < sz); (dir ? i-- : i++)) {
		int cur = (rc) ? a[i][v] : a[v][i];
		while (cur >= stck.back().first) stck.pop_back();
		if (rc) store[i][v] = stck.back().second;
		else store[v][i] = stck.back().second;
		stck.push_back(pii(cur, i));
	}
}

map<pii, vector<int>> occ[2]; // row, then column

int cnt_leq(vector<int> &v, int i) {
	int mn = -1;
	int mx = v.size();
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (v[cur] <= i) mn = cur;
		else mx = cur;
	}
	return mx;
}

void print(rect &r) {
	cout << r.first.first << ' ' << r.first.second << ' ' << r.second.first << ' ' << r.second.second << '\n';
}

vector<rect> cands;

long long count_rectangles(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
	for (int i = 0; i < n; i++) {
		make(prv[0], 0, 0, a, i);
		make(nxt[0], 0, 1, a, i);
	}
	for (int i = 0; i < m; i++) {
		make(prv[1], 1, 0, a, i);
		make(nxt[1], 1, 1, a, i);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int suc = 0;
			for (int t = 0; t < 2; t++) {
				int rcpos = (t ? i : j);
				if (nxt[t][i][j] != -1 && prv[t][i][j] != -1) {
					suc++;
					if (nxt[t][i][j]) {
						occ[t][pii(prv[t][i][j]+1, nxt[t][i][j]-1)].push_back(i^j^rcpos);
					}
				}
			}
			if (suc == 2) {
				// cerr << i << ' ' << j << '\n';
				cands.push_back(rect(pii(prv[1][i][j]+1, prv[0][i][j]+1), pii(nxt[1][i][j]-1, nxt[0][i][j]-1)));
			}
		}
	}
	for (auto &it: occ[0]) {
		sort(it.second.begin(), it.second.end());
		int p = 0;
		int pv = -1;
		for (int i = 0; i < it.second.size(); i++) {
			if (it.second[i] == pv) continue;
			pv = it.second[i];
			swap(it.second[p++], it.second[i]);
		}
		it.second.resize(p);
	}
	for (auto &it: occ[1]) {
		sort(it.second.begin(), it.second.end());
		int p = 0;
		int pv = -1;
		for (int i = 0; i < it.second.size(); i++) {
			if (it.second[i] == pv) continue;
			pv = it.second[i];
			swap(it.second[p++], it.second[i]);
		}
		it.second.resize(p);
	}
	int ans = 0;
	// cerr << cands.size() << '\n';
	sort(cands.begin(), cands.end());
	int p = 0;
	rect pv(pii(-1, -1), pii(-1, -1));
	for (int i = 0; i < cands.size(); i++) {
		if (cands[i] == pv) continue;
		pv = cands[i];
		swap(cands[p++], cands[i]);
	}
	cands.resize(p);
	for (rect r: cands) {
		// print(r);
		pii up = r.first;
		pii down = r.second;
		pii xrange = pii(up.first, down.first);
		pii yrange = pii(up.second, down.second);
		if ((cnt_leq(occ[0][yrange], xrange.second)-cnt_leq(occ[0][yrange], xrange.first-1) == xrange.second-xrange.first+1)
			&& (cnt_leq(occ[1][xrange], yrange.second)-cnt_leq(occ[1][xrange], yrange.first-1) == yrange.second-yrange.first+1)) {

			// cerr << xrange.second-xrange.first+1 << ' ' << cnt_leq(occ[0][yrange], xrange.second)
			// << ' ' << cnt_leq(occ[0][yrange], xrange.first-1) << '\n';
			// print(r);
			ans++;
		}

	}
	return ans;
}

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

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for (int i = 0; i < it.second.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for (int i = 0; i < it.second.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0; i < cands.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

• 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: 0 / 28