Submission #299087

#	Time	Username	Problem	Language	Result	Execution time	Memory
299087		TMJN	Rectangles (IOI19_rect)	C++17	37 / 100	5035 ms	326500 KiB

rect

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

set<int>sth[2500],stw[2500];
set<pair<int,int>>stph[2500],stpw[2500];
vector<pair<int,pair<int,int>>>p;
int H,W,res;



long long count_rectangles(vector<vector<int>>a){
	H=a.size();
	W=a[0].size();
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			p.push_back({a[i][j],{i,j}});
		}
	}
	p.push_back({0xE869120,{-1,-1}});
	sort(p.begin(),p.end());
	for(int i=0;i<H;i++){
		for(int j=-1;j<=W;j++){
			sth[i].insert(j);
		}
	}
	for(int i=0;i<W;i++){
		for(int j=-1;j<=H;j++){
			stw[i].insert(j);
		}
	}
	for(int i=0;i<p.size()-1;i++){
		if(i&&p[i-1].first==p[i].first)continue;
		for(int j=i;p[i].first==p[j].first;j++){
			sth[p[j].second.first].erase(p[j].second.second);
			stw[p[j].second.second].erase(p[j].second.first);
		}
		vector<pair<pair<int,int>,pair<int,int>>>pp;
		for(int j=i;p[i].first==p[j].first;j++){
			int lx,rx,ly,ry;
			auto it=sth[p[j].second.first].lower_bound(p[j].second.second);
			ry=*it;
			it--;
			ly=*it;
			auto it2=stw[p[j].second.second].lower_bound(p[j].second.first);
			rx=*it2;
			it2--;
			lx=*it2;
			lx++;
			rx--;
			ly++;
			ry--;
			if(lx<=0||ly<=0||H-1<=rx||W-1<=ry)continue;
			stph[p[j].second.first].insert({ly,ry});
			stpw[p[j].second.second].insert({lx,rx});
		}
		for(int j=i;p[i].first==p[j].first;j++){
			int lx,rx,ly,ry;
			auto it=sth[p[j].second.first].lower_bound(p[j].second.second);
			ry=*it;
			it--;
			ly=*it;
			auto it2=stw[p[j].second.second].lower_bound(p[j].second.first);
			rx=*it2;
			it2--;
			lx=*it2;
			lx++;
			rx--;
			ly++;
			ry--;
			if(lx<=0||ly<=0||H-1<=rx||W-1<=ry)continue;
			bool f=true;
			for(int k=lx;k<=rx;k++){
				if(stph[k].find({ly,ry})==stph[k].end()){
					f=false;
					break;
				}
			}
			for(int k=ly;k<=ry;k++){
				if(stpw[k].find({lx,rx})==stpw[k].end()){
					f=false;
					break;
				}
			}
			if(f){
				pp.push_back({{lx,rx},{ly,ry}});
			}
		}
		sort(pp.begin(),pp.end());
		pp.erase(unique(pp.begin(),pp.end()),pp.end());
		res+=pp.size();
	}
	return res;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:32:15: 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]
   32 |  for(int i=0;i<p.size()-1;i++){
      |              ~^~~~~~~~~~~

• 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