제출 #1179338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179338		Gr1sen	Rectangles (IOI19_rect)	C++20	25 / 100	5097 ms	89576 KiB

rect

#include "rect.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vp vector<pi>

void print(vvi &L) {
	cerr << "{";
	for (auto i : L) {
		cerr << "{";
		for (auto j : i) cerr << j << ", ";
		cerr << "},\n";
	}
	cerr << endl;
}

void print(vi &L) {
	cerr << "{";
	for (auto i : L) cerr << i << ", ";
	cerr << "}" << endl;
}

ll count_rectangles(vector<vector<int>> B) {
	if (B.size() <= 2 || B[0].size() <= 2) return 0;
	vvi CL(B.size(), vi(B[0].size(), -1));
	vvi CR = CL, RT = CL, RB = CL;
	vp L;
	for (int j = 0; j < B.size(); j++) {
		//cerr << "j : " << j << endl;
		L.clear();
		for (int i = B[0].size()-1; i > -1; i--) {
			//cerr << "i : " << i << endl;
			while (L.size() && L.back().first < B[j][i]) L.pop_back();
			;
			//cerr << "oink" << endl;
			if (L.size()) CL[j][i] = L.back().second;
			else CL[j][i] = B[0].size()-1;
			L.push_back({B[j][i], i});
		}
	}
	for (int j = 0; j < B.size(); j++) {
		//cerr << "j : " << j << endl;
		L.clear();
		for (int i = 0; i < B[0].size(); i++) {
			//cerr << "i : " << i << endl;
			while (L.size() && L.back().first < B[j][i]) L.pop_back();
			;
			//cerr << "oink" << endl;
			if (L.size()) CR[j][i] = L.back().second;
			else CR[j][i] = 0;
			L.push_back({B[j][i], i});
		}
	}
	for (int i = 0; i < B[0].size(); i++) {
		//cerr << "j : " << j << endl;
		L.clear();
		for (int j = B.size()-1; j > -1; j--) {
			//cerr << "i : " << i << endl;
			while (L.size() && L.back().first < B[j][i]) L.pop_back();
			;
			//cerr << "oink" << endl;
			if (L.size()) RT[j][i] = L.back().second;
			else RT[j][i] = B.size()-1;
			L.push_back({B[j][i], j});
		}
	}
	for (int i = 0; i < B[0].size(); i++) {
		//cerr << "j : " << j << endl;
		L.clear();
		for (int j = 0; j < B.size(); j++) {
			//cerr << "i : " << i << endl;
			while (L.size() && L.back().first < B[j][i]) L.pop_back();
			;
			//cerr << "oink" << endl;
			if (L.size()) RB[j][i] = L.back().second;
			else RB[j][i] = 0;
			L.push_back({B[j][i], j});
		}
	}
	//*
	cerr << "CL\n";
	print(CL);
	cerr << "CR\n";
	print(CR);
	cerr << "RT\n";
	print(RT);
	cerr << "RB\n";
	print(RB);
	//*/
	ll t = 0;
	/*
	for (int i = 0; i < B.size(); i++) {
		for (int j = 0; j < B[0].size(); j++) {
			//t += (B[i][j]);
		}
	}//*/

	for (int c1 = 0; c1 < B.size(); c1++) {
		for (int c2 = c1+2; c2 < B.size(); c2++) {
			cerr << "\n" << "c1 : " << c1 << ", c2 : " << c2 << ", t : " << t << endl;
			vi L(B[0].size(), 0);
			for (int r1 = 0; r1 < B[0].size(); r1++) {
				L[r1] = (RT[c1][r1] >= c2 && RB[c2][r1] <= c1);
			}
			cerr << c1 << " " << c2 << " : ";
			print(L);
			for (int r1 = 0; r1 < B[0].size(); r1++) {
				if (!L[r1+1]) continue;
				for (int r2 = r1+2; r2 < B[0].size(); r2++) {
					if (!L[r2-1]) break;
					//cerr << "oink" << endl;
					bool q = 0;
					for (int c = c1+1; c < c2; c++) {
						if (CL[c][r1] >= r2 && CR[c][r2] <= r1) continue;
						q = 1;
						break;
					}
					t += !q;
				}
			}
		}
	}

	return t;
}

• 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