제출 #264545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
264545		kdh9949	Rectangles (IOI19_rect)	C++17	100 / 100	4892 ms	531064 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

using S = pair<pii, int>;
using SS = pair<pii, pii>;

ll count_rectangles(vector<vint> a) {
	int n = a.size(), m = a[0].size();

	vector<S> rp, cp;
	vector<vint> um(n, vint(m)), dm(n, vint(m)), lm(n, vint(m)), rm(n, vint(m));
	for(int i = 1; i < n - 1; i++) {
		stack<int> st;
		for(int j = 0; j < m; j++) {
			while(!st.empty() && a[i][st.top()] < a[i][j]) {
				st.pop();
				if(!st.empty()) rp.emplace_back(pii(st.top() + 1, j - 1), i);
			}
			while(!st.empty() && a[i][st.top()] == a[i][j]) st.pop();
			if(!st.empty()) lm[i][j] = st.top() + 1;
			st.push(j);
		}
		while(!st.empty()) st.pop();
		for(int j = m - 1; j >= 0; j--) {
			while(!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
			if(!st.empty()) rm[i][j] = st.top() - 1;
			st.push(j);
		}
	}
	for(int i = 1; i < m - 1; i++) {
		stack<int> st;
		for(int j = 0; j < n; j++) {
			while(!st.empty() && a[st.top()][i] < a[j][i]) {
				st.pop();
				if(!st.empty()) cp.emplace_back(pii(st.top() + 1, j - 1), i);
			}
			while(!st.empty() && a[st.top()][i] == a[j][i]) st.pop();
			if(!st.empty()) um[j][i] = st.top() + 1;
			st.push(j);
		}
		while(!st.empty()) st.pop();
		for(int j = n - 1; j >= 0; j--) {
			while(!st.empty() && a[st.top()][i] <= a[j][i]) st.pop();
			if(!st.empty()) dm[j][i] = st.top() - 1;
			st.push(j);
		}
	}
	
	sort(all(rp));
	sort(all(cp));
	vector<pii> rseg;
	vector<vint> rS(m, vint(m, -1)), rE(m, vint(m, -1));
	for(int i = 0, j; i < rp.size(); i = j) {
		for(j = i + 1;
			j < rp.size() && rp[i].x == rp[j].x && rp[j].y - rp[i].y == j - i;
			j++);
		pii cur = rp[i].x;
		if(rS[cur.x][cur.y] < 0) rS[cur.x][cur.y] = rseg.size();
		rE[cur.x][cur.y] = rseg.size();
		rseg.emplace_back(rp[i].y, rp[j - 1].y);
	}
	vector<pii> cseg;
	vector<vint> cS(n, vint(n, -1)), cE(n, vint(n, -1));
	for(int i = 0, j; i < cp.size(); i = j) {
		for(j = i + 1;
			j < cp.size() && cp[i].x == cp[j].x && cp[j].y - cp[i].y == j - i;
			j++);
		pii cur = cp[i].x;
		if(cS[cur.x][cur.y] < 0) cS[cur.x][cur.y] = cseg.size();
		cE[cur.x][cur.y] = cseg.size();
		cseg.emplace_back(cp[i].y, cp[j - 1].y);
	}

	vector<ll> ans;
	for(int i = 1; i < n - 1; i++) {
		for(int j = 1; j < m - 1; j++) {
			int A = um[i][j], B = dm[i][j], C = lm[i][j], D = rm[i][j];
			if(!A || !B || !C || !D) continue;
			if(rS[C][D] < 0 || cS[A][B] < 0) continue;

			int l = rS[C][D] - 1, r = rE[C][D];
			while(l < r) {
				int m = (l + r + 1) >> 1;
				if(rseg[m].x <= A) l = m;
				else r = m - 1;
			}
			if(!(rS[C][D] <= l && l <= rE[C][D] && B <= rseg[l].y)) continue;

			l = cS[A][B] - 1; r = cE[A][B];
			while(l < r) {
				int m = (l + r + 1) >> 1;
				if(cseg[m].x <= C) l = m;
				else r = m - 1;
			}
			if(!(cS[A][B] <= l && l <= cE[A][B] && D <= cseg[l].y)) continue;

			ans.push_back(A ^ (ll(B) << 12) ^ (ll(C) << 24) ^ (ll(D) << 36));
		}
	}

	sort(all(ans));
	return int(unique(all(ans)) - ans.begin());
}

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

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0, j; i < rp.size(); i = j) {
      |                    ~~^~~~~~~~~~~
rect.cpp:75:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    j < rp.size() && rp[i].x == rp[j].x && rp[j].y - rp[i].y == j - i;
      |    ~~^~~~~~~~~~~
rect.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 0, j; i < cp.size(); i = j) {
      |                    ~~^~~~~~~~~~~
rect.cpp:86:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    j < cp.size() && cp[i].x == cp[j].x && cp[j].y - cp[i].y == j - 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: 28 / 28