Submission #1060754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060754		jamesbamber	Rectangles (IOI19_rect)	C++17	10 / 100	743 ms	960780 KiB

rect

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

struct segment{
	vector<int> tr;
	int sz;

	segment(vector<int> &v){
		sz = 1;
		while(sz <= v.size()) sz *= 2;
		tr.resize(2*sz);

		for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
		for(int i=sz; --i;) tr[i] = max(tr[2*i], tr[2*i+1]); 
	}
	segment() {}

	int query(int l, int r){
		int ans = 0;
		for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
			if(l & 1) ans = max(ans, tr[l++]);
			if(r & 1) ans = max(ans, tr[--r]);
		}
		return ans;
	}
};

struct segment2d{
	vector<segment> tr;
	int sz;

	segment2d(vector<vector<int>> &v){
		sz = 1;
		while(sz <= v.size()) sz *= 2;
		tr.resize(2*sz);

		int sz2 = 1;
		while(sz2 <= v[0].size()) sz2 *= 2;

		vector<int> ilvuoto(sz2);

		for(int i=0; i<v.size(); i++) tr[i+sz] = segment(v[i]);
		for(int i=v.size(); i<sz; i++) tr[i+sz] = segment(ilvuoto);
		for(int i=sz; --i;){
			vector<int> treesus(sz2);
			for(int j=0; j<sz2; j++) treesus[j] = max(tr[2*i].tr[j+sz2], tr[2*i+1].tr[j+sz2]); 
			tr[i] = segment(treesus);
		}
	}

	int query(int l, int r, int ql, int qr){
		int ans = 0;
		for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
			if(l & 1) ans = max(ans, tr[l++].query(ql, qr));
			if(r & 1) ans = max(ans, tr[--r].query(ql, qr));
		}
		return ans;
	}
};

struct segment2{
	vector<int> tr;
	int sz;

	segment2(vector<int> &v){
		sz = 1;
		while(sz <= v.size()) sz *= 2;
		tr.resize(2*sz);

		for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
		for(int i=v.size(); i<sz; i++) tr[i+sz] = v.size();
		for(int i=sz; --i;) tr[i] = min(tr[2*i], tr[2*i+1]); 
	}
	segment2() {}

	int query(int l, int r){
		int ans = 1e9;
		for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
			if(l & 1) ans = min(ans, tr[l++]);
			if(r & 1) ans = min(ans, tr[--r]);
		}
		return ans;
	}
};

struct segment22d{
	vector<segment2> tr;
	int sz;

	segment22d(vector<vector<int>> &v){
		sz = 1;
		while(sz <= v.size()) sz *= 2;
		tr.resize(2*sz);

		int sz2 = 1;
		while(sz2 <= v[0].size()) sz2 *= 2;

		vector<int> ilgrosso(sz2, v[0].size());

		for(int i=0; i<v.size(); i++) tr[i+sz] = segment2(v[i]);
		for(int i=v.size(); i<sz; i++) tr[i+sz] = segment2(ilgrosso);
		for(int i=sz; --i;){
			vector<int> treesus(sz2);
			for(int j=0; j<sz2; j++) treesus[j] = min(tr[2*i].tr[j+sz2], tr[2*i+1].tr[j+sz2]); 
			tr[i] = segment2(treesus);
		}
	}

	int query(int l, int r, int ql, int qr){
		int ans = 1e9;
		for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){
			if(l & 1) ans = min(ans, tr[l++].query(ql, qr));
			if(r & 1) ans = min(ans, tr[--r].query(ql, qr));
		}
		return ans;
	}
};

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size();
	int m = a[0].size();

	vector<vector<int>> up(n, vector<int>(m, -1)), down(n, vector<int>(m, n)), left(n, vector<int>(m, -1)), right(n, vector<int>(m, m));

	//right
	for(int i=0; i<n; i++){
		stack<int> s;
		for(int j=0; j<m; j++){
			while(s.size() and a[i][s.top()] < a[i][j]){
				right[i][s.top()] = j;
				s.pop();
			}
			s.push(j);
		}
	}

	//left
	for(int i=0; i<n; i++){
		stack<int> s;
		for(int j=m-1; j>=0; j--){
			while(s.size() and a[i][s.top()] < a[i][j]){
				left[i][s.top()] = j;
				s.pop();
			}
			s.push(j);
		}
	}

	//up
	for(int j=0; j<m; j++){
		stack<int> s;
		for(int i=n-1; i>=0; i--){
			while(s.size() and a[s.top()][j] < a[i][j]){
				up[s.top()][j] = i;
				s.pop();
			}
			s.push(i);
		}
	}

	//down
	for(int j=0; j<m; j++){
		stack<int> s;
		for(int i=0; i<n; i++){
			while(s.size() and a[s.top()][j] < a[i][j]){
				down[s.top()][j] = i;
				s.pop();
			}
			s.push(i);
		}
	}

	int ans = 0;

	segment2d stright(right), stdown(down);
	segment22d stleft(left), stup(up);
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			int l = left[i][j], r = right[i][j], u = up[i][j], d = down[i][j];
			if(l == -1 or r == m or u == -1 or d == n) continue;
			if(
				l == stleft.query(u+1, d, l+1, r) and 
				r == stright.query(u+1, d, l+1, r) and 
				u == stup.query(u+1, d, l+1, r) and 
				d == stdown.query(u+1, d, l+1, r)
			) ans++;

			// cerr << i << " " << j << endl;
			// cerr << l << " " << r << " " << u << " " << d << endl;
			// cerr << stleft.query(u+1, d, l+1, r) << " " << stright.query(u+1, d, l+1, r) << " " << stup.query(u+1, d, l+1, r) << " " << stdown.query(u+1, d, l+1, r) << endl;
		}
	}

	// for(int i=0; i<n; i++){
	// 	for(int j=0; j<m; j++){
	// 		cout << up[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	return ans;
}

Compilation message (stderr)

rect.cpp: In constructor 'segment::segment(std::vector<int>&)':
rect.cpp:11:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
      |                ~^~~~~~~~~
rect.cpp: In constructor 'segment2d::segment2d(std::vector<std::vector<int> >&)':
rect.cpp:35:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:39:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   while(sz2 <= v[0].size()) sz2 *= 2;
      |         ~~~~^~~~~~~~~~~~~~
rect.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=0; i<v.size(); i++) tr[i+sz] = segment(v[i]);
      |                ~^~~~~~~~~
rect.cpp: In constructor 'segment2::segment2(std::vector<int>&)':
rect.cpp:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0; i<v.size(); i++) tr[i+sz] = v[i];
      |                ~^~~~~~~~~
rect.cpp: In constructor 'segment22d::segment22d(std::vector<std::vector<int> >&)':
rect.cpp:93:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:97:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   while(sz2 <= v[0].size()) sz2 *= 2;
      |         ~~~~^~~~~~~~~~~~~~
rect.cpp:101:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i=0; i<v.size(); i++) tr[i+sz] = segment2(v[i]);
      |                ~^~~~~~~~~

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