Submission #1073466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073466		n1k	Rectangles (IOI19_rect)	C++17	0 / 100	1335 ms	360612 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

int n, m;

vector<vector<array<int, 3>>> h;

vector<vector<array<int, 2>>> get(){
	vector<vector<array<int, 2>>> l(n, vector<array<int, 2>>(m));
	for(int r=1; r+1<h.size(); r++){
		vector<array<int, 3>> st = {{h[r][0]}};
		for(int c=1; c+1<h[0].size(); c++){
			while(st.size() and st.back()[0]<=h[r][c][0]){
				st.pop_back();
			}
			l[h[r][c][1]][h[r][c][2]] = (st.size()?array<int, 2>{st.back()[1], st.back()[2]}:array<int, 2>{-1, -1});
			st.push_back(h[r][c]);
		}
	}
	return l;
}

void rot(){
	vector<vector<array<int, 3>>> hh(h[0].size(), vector<array<int, 3>>(h.size()));
	for(int r=0; r<h.size(); r++){
		for(int c=0; c<h[0].size(); c++){
			hh[c][h.size() - r - 1] = h[r][c];
		}
	}
	h = hh;
}

long long count_rectangles(vector<vector<int>> a) {
	n = a.size(), m = a[0].size();
	h.assign(a.size(), vector<array<int, 3>>(a[0].size()));
	vector<array<int, 2>> order;
	for(int r=0; r<a.size(); r++){
		for(int c=0; c<a[0].size(); c++){
			h[r][c] = {a[r][c], r, c};
		}
	}
	auto l=get();
	rot();
	auto d = get();
	rot();
	auto ri = get();
	rot();
	auto u = get();
	rot();

	auto find = [&](int r1, int r2, int c1, int c2){
		array<int, 3> ll={int(1e9)}, dd={int(-1e9)}, riri={int(-1e9)}, uu={int(1e9)};
		for(int r=r1+1; r<r2; r++){
			for(int c=c1+1; c<c2; c++){
				ll = min(ll, {l[r][c][1], r, c});
				dd = max(dd, {d[r][c][0], r, c});
				riri = max(riri, {ri[r][c][1], r, c});
				uu = min(uu, {u[r][c][0], r, c});
			}
		}
		set<array<int, 2>> s;
		s.insert({ll[1], ll[2]});
		s.insert({dd[1], dd[2]});
		s.insert({riri[1], riri[2]});
		s.insert({uu[1], uu[2]});
		return s;
	};

	vector g(n, vector<vector<array<int, 2>>>(m));
	for(int r=1; r+1<n; r++){
		for(int c=1; c+1<m; c++){
			// find()
			int r1 = u[r][c][0], r2 = d[r][c][0];
			int c1 = l[r][c][1], c2 = ri[r][c][1];
			if(min({r1, r2, c1, c2})==-1){
				g[r][c].push_back({-1, -1});
			}else{
				for(auto p:find(r1, r2, c1, c2)){
					g[r][c].push_back(p);
				}
			}
		}
	}
	vector mem(n, vector<int>(m, -1));
	vector vis(n, vector<int>(m));
	vector bd(n, vector<int>(m));


	function<void(int, int)> dfsord = [&](int r, int c){
		if(vis[r][c]) return;
		vis[r][c]=1;
		int r1 = u[r][c][0], r2 = d[r][c][0];
		int c1 = l[r][c][1], c2 = ri[r][c][1];
		if(min({r1, r2, c1, c2})==-1){
			bd[r][c] = 1;
			return;
		}
		for(int rr=r1+1; rr<r2; rr++){
			for(int cc=c1+1; cc<c2; cc++){
				bd[r][c] |= bd[rr][cc];
				dfsord(rr, cc);
			}
		}
		if(not bd[r][c])
			order.push_back({r, c});
	};
	for(int r=1; r+1<n; r++){
		for(int c=1; c+1<m; c++){
			if(vis[r][c]) continue;
			dfsord(r, c);
		}
	}

	function<void(int, int)> dfs = [&](int r, int c){
		if(vis[r][c]) return;
		vis[r][c]=1;
		if(mem[r][c]!=-1) mem[r][c];
		bool ok = 1;
		for(auto [rr, cc]:g[r][c]){
			if(rr==r and cc==c){
				continue;
			}
			if(rr==-1 and cc==-1){
				ok = 0;
				continue;
			}
			dfs(rr, cc);
			ok &= mem[rr][cc];
			l[r][c][1] = min(l[r][c][1], l[rr][cc][1]);
			d[r][c][0] = max(d[r][c][0], d[rr][cc][0]);
			ri[r][c][1] = max(ri[r][c][1], ri[rr][cc][1]);
			u[r][c][0] = min(u[r][c][0], u[rr][cc][0]);
		}
		mem[r][c] = ok;
	};

	vis.assign(n, vector<int>(m));
	long long ans = 0;
	for(auto [r, c]:order){
		if(vis[r][c]) continue;
		dfs(r, c);
		assert(mem[r][c]!=-1);
		ans += mem[r][c];

		if(mem[r][c]){
			for(int rr=u[r][c][0]+1; rr<d[r][c][0]; rr++){
				for(int cc=l[r][c][1]+1; cc<ri[r][c][1]; cc++){
					mem[rr][cc] = mem[r][c];
					vis[rr][cc] = 1;
				}
			}
		}
		if(mem[r][c]==1){
		}
	}
	// build graph
	/*
	for(int r=0; r<n; r++){
		for(int c=0; c<m; c++){
			cerr<<mark[r][c]<<" ";
		}
		cerr<<endl;
	}
	for(int r=0; r<u.size();r++){
		for(int c=0; c<u[0].size(); c++){
			cerr<<u[r][c][0]<<" "<<u[r][c][1]<<" | ";
		}
		cerr<<endl;
	}
	for(int r=0; r<h.size(); r++){
		for(int c=0; c<h[0].size(); c++){
			cerr<<h[r][c][0]<<" ";
		}
		cerr<<endl;
	}
	*/
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::vector<std::array<int, 2> > > get()':
rect.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int r=1; r+1<h.size(); r++){
      |               ~~~^~~~~~~~~
rect.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int c=1; c+1<h[0].size(); c++){
      |                ~~~^~~~~~~~~~~~
rect.cpp: In function 'void rot()':
rect.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int r=0; r<h.size(); r++){
      |               ~^~~~~~~~~
rect.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int c=0; c<h[0].size(); c++){
      |                ~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int r=0; r<a.size(); r++){
      |               ~^~~~~~~~~
rect.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int c=0; c<a[0].size(); c++){
      |                ~^~~~~~~~~~~~

• 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