제출 #1179506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179506		Gr1sen	Rectangles (IOI19_rect)	C++20	37 / 100	5111 ms	446964 KiB

rect

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

using namespace std;

#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vp vector<pi>
#define ss set<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;
}

void print(ss &S) {
	cerr << "{";
	for (auto i : S) {
		cerr << "{" << i.first << ", " << i.second << "}, ";
	}
	cerr << "}\n";
}

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]);
		}
	}//*/
	ss S2;
	for (int r1 = 0; r1 < B[0].size(); r1++) {
		for (int r2 = r1+2; r2 < B[0].size(); r2++) {
			S2.insert({r1, r2});
		}
	}

	for (int c1 = 0; c1 < B.size(); c1++) {
		vi L2(B[0].size(), 1);
		ss S = S2;
		for (int c2 = c1+2; c2 < B.size(); c2++) {
			//cerr << "\n" << "c1 : " << c1 << ", c2 : " << c2 << ", t : " << t << endl;
			vi L(B[0].size(), 0);
			int oi = 1;
			for (int r1 = 0; r1 < B[0].size(); r1++) {
				if (RT[c1][r1] >= c2 && RB[c2][r1] <= c1) {
					L[r1] = oi;
					continue;
				}
				oi++;
			}
			L2 = L;
			//cerr << c1 << " " << c2 << " : ";
			//print(L);
			ss S3;
			for (auto i = S.begin(); i != S.end(); i++) {
				int r1 = (*i).first, r2 = (*i).second;
				/*
				if (L[r1+1] != L[r2-1] || L[r1+1] == 0) {
					S3.insert({r1, r2});
					continue;
				}//*/
				if (CL[c2-1][r1] >= r2 && CR[c2-1][r2] <= r1) {
					if (L[r1+1] != L[r2-1] || L[r1+1] == 0) continue;
					t += 1;
					continue;
				}
				S3.insert({r1, r2});
			}
			//print(S3);
			for (auto i : S3) {
				S.erase(i);
			}
			//print(S);
		}
	}

	return t;
}

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