제출 #824789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
824789		tolbi	Rectangles (IOI19_rect)	C++17	0 / 100	3197 ms	114004 KiB

rect

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename T> istream& operator>>(istream& is, vector<T> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> arr){for (auto &it : arr) os<<it<<" "; return os;}
template<typename T,size_t Y> istream& operator>>(istream& is, array<T,Y> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T,size_t Y> ostream& operator<<(ostream& os, array<T,Y> arr){for (auto &it : arr) os<<it<<" "; return os;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it :x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "rect.h"
struct AHMET23{
	vector<vector<int>> arr;
	int n,m;
	AHMET23(int _n, int _m):n(_n),m(_m){
		arr.resize(_n,vector<int>(_m,1));
	}
	void update(int x, int y){
		arr[x][y]=0;
	}
	int findup(int x, int y){
		while (x>=0 && !arr[x][y])x--;
		return x+1;
	}
	int finddown(int x, int y){
		while (x<n && !arr[x][y])x++;
		return x-1;
	}
	int findnext(int x, int y){
		while (y<m && !arr[x][y])y++;
		return y-1;
	}
	int findprev(int x, int y){
		while (y>=0 && !arr[x][y])y--;
		return y+1;
	}
	int query(int xl, int xr, int yl, int yr){
		int rval = 0;
		for (int x = xl; x <= xr; x++){
			for (int y = yl; y <= yr; y++){
				rval+=arr[x][y];
			}
		}
		return rval;
	}
	void print(){
		for (int i = 0; i < n; i++){
			cout<<arr[i]<<endl;
		}
	}
};
long long count_rectangles(vector<vector<int>> arr) {
	vector<pair<int,pair<int,int>>> vals;
	int n = arr.size();
	int m = arr[0].size();
	AHMET23 ds(n,m);
	AHMET23 ds2(n,m);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			vals.push_back({arr[i][j],{i,j}});
		}
	}
	sortarr(vals);
	auto checkvalid = [&](int xl, int xr, int yl, int yr)->bool{
		if (xl==0 || xr==n-1 || yl==0 || yr==m-1) return false;
		if (ds.query(xl,xr,yl,yr)!=0) return false;
		ll tot = 0;
		tot+=ds2.query(xl,xr,yl-1,yl-1);
		tot+=ds2.query(xl,xr,yr+1,yr+1);
		tot+=ds2.query(xl-1,xl-1,yl,yr);
		tot+=ds2.query(xr+1,xr+1,yl,yr);
		if (tot!=2*(xr-xl+1+yr-yl+1)) return false;
		return true;
	};
	ll ans = 0;
	vector<pair<int,int>> kal;
	set<pair<int,int>> stt;
	for (int i = 0; i < vals.size(); i++){
		if (i<vals.size()-1 && vals[i].first==vals[i+1].first){
			kal.push_back(vals[i].second);
		}
		else {
			kal.push_back(vals[i].second);
			for (auto &it : kal){
				stt.insert(it);
				ds.update(it.first,it.second);
			}
			cout<<ans<<endl;
			ds.print();
			set<array<int,4>> st;
			for (auto &it : kal){
				int x = it.first;
				int y = it.second;
				int xl = ds.findup(it.first,it.second);
				int xr = ds.finddown(it.first,it.second);
				int yl = ds.findprev(it.first,it.second);
				int yr = ds.findnext(it.first,it.second);
				if (st.find({xl,xr,yl,yr})!=st.end()) continue;
				int hayd = 0;
				if (stt.find({x,yr+1})!=stt.end()) hayd++;
				if (stt.find({x,yl-1})!=stt.end()) hayd++;
				if (stt.find({xl-1,y})!=stt.end()) hayd++;
				if (stt.find({xr+1,y})!=stt.end()) hayd++;
				if (!hayd && checkvalid(xl,xr,yl,yr)) ans++;
				st.insert({xl,xr,yl,yr});
			}
			cout<<ans<<endl;
			cout<<endl;
			for (auto &it : kal){
				ds2.update(it.first,it.second);
			}
			kal.clear();

		}
	}
	return ans;
}

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

rect.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:98: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]
   98 |  for (int i = 0; i < vals.size(); i++){
      |                  ~~^~~~~~~~~~~~~
rect.cpp:99:8: 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]
   99 |   if (i<vals.size()-1 && vals[i].first==vals[i+1].first){
      |       ~^~~~~~~~~~~~~~

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