Submission #1060791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060791		jamesbamber	Rectangles (IOI19_rect)	C++17	59 / 100	860 ms	1048576 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 = v[0].size();

		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+tr[2*i].sz], tr[2*i+1].tr[j+tr[2*i+1].sz]); 
			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] = 1e9;
		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 = v[0].size();

		vector<int> ilgrosso(sz2, 1e9);

		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, 1e9);
			for(int j=0; j<sz2; j++) treesus[j] = min(tr[2*i].tr[j+tr[2*i].sz], tr[2*i+1].tr[j+tr[2*i+1].sz]); 
			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;

	set<array<int, 4>> grind;

	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)
			) grind.insert({l, r, u, d});
			// 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 << left[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	return grind.size();
}

/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣠⣤⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⡴⡖⣻⡟⣛⡛⣿⣿⣿⣿⣻⣿⣿⡟⠛⠳⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣯⣾⣤⣹⣷⣿⣿⡿⣿⡿⣿⣿⣿⣿⣼⣧⣄⣚⠉⠛⠶⢶⣤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⣙⠾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢘⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⠿⠛⠛⠛⠛⠿⠿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⡿⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⣿⣿⣯⡿⠀⠀⠀⠀⠀⠀⠀⠠⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⢀⣀⣄⡀⠀⠀⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⡇⣠⣾⣿⣿⣶⣶⣶⣶⣿⣦⡀⠀⠻⣤⣶⣾⣿⣿⣿⣿⣿⠿⠿⣿⣶⣄⠈⣿⡇⢹⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣿⣿⣿⣿⠁⡿⠟⣉⣽⣿⣿⣿⣿⣿⣿⡗⠀⠀⢈⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣦⣹⡇⣽⣿⣿⣿⣿⣿⣿⣿⠀⣀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⠴⠂⠀⣀⣤⣾⣿⣿⣿⣿⣿⡿⠀⢱⣿⣿⣏⣛⣛⣣⢬⣹⢿⠏⠀⢀⣼⣿⣯⡛⠒⢽⣿⣥⡿⣿⣿⣿⣿⣿⣿⣇⣿⣿⣿⣿⣿⣿⣿⣍⣉⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣰⣿⠤⣶⣿⠿⣻⣿⣿⣿⣿⣿⣿⡇⠀⠀⠋⠀⠉⠉⠁⠒⠉⠀⠀⡀⠀⠀⢿⣿⣿⠛⠦⠀⠀⢸⡿⠋⠋⠙⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡛⣆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠈⠉⠉⢡⣰⣥⠾⣿⣿⣿⣿⣿⣿⣿⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠁⠀⠀⢸⡿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⣿⣿⡹⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⡕⠽⣾⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⣶⣶⣤⣶⣿⣷⣼⣧⡀⠀⠀⠀⠠⠀⢀⣰⣿⣿⣿⣿⣿⣿⣷⣻⣿⣿⣿⣿⣿⣿⢿⣿⣶⠄
⠀⠀⠀⠀⠀⠀⠀⠀⡞⠀⢀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⢠⠎⠻⠯⣍⠙⠟⢻⣿⠿⣿⠟⠀⠀⠀⣶⣦⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⠳⣌⢣⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣡⠖⠙⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⠀⠈⠀⢀⣴⣿⠟⠁⢾⣿⣷⣄⡀⡀⠀⠀⠿⠟⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠈⠁⠀⣧
⠀⠀⠀⠀⠀⠀⠀⣼⠃⠀⠀⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡤⠀⠀⠀⣠⣾⣾⠟⢛⣁⣤⣠⣼⣿⣿⣿⣿⣿⣶⣄⣠⣾⣫⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠙⠷⣦⣾⣿⠟⢿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⣱⠀⣼⣿⡯⡿⠾⠛⠛⠛⠛⠛⢻⣿⣿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠋⠀⠀⣻⣿⣿⣿⣿⣿⣿⣿⣷⣿⣷⠃⢿⡟⠀⠀⠰⣦⣤⣤⣴⣶⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡶⢿⣷⣦⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⠈⠀⠀⠀⠀⠀⠛⠉⠛⠛⠛⠻⣿⢟⣉⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠘⣼⣌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⣽⣷⡶⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣷⣶⣠⣤⣠⣦⡡⣠⣼⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⠦⣽⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⠉⡆⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠿⠟⠛⠉⢿⣿⣿⣿⣿⣿⣿⣿⣿⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣟⡿⣻⣿⠟⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⠴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣟⡛⠁⠘⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢀⣀⣀⣀⣀⣀⣤⢴⣾⠿⣉⣽⠞⠁⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣻⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⡿⠒⠾⣿⣭⣌⡉⠉⠙⠳⠟⢁⣐⠛⠃⠀⢐⡶⠉⠉⠻⣿⣿⣿⣿⣯⡙⢿⣯⣉⠉⠻⣿⣿⣏⢿⣿⣿⣿⣿⣿⣬⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣧⢐⡦⣌⠙⢮⡹⠛⢶⣤⣶⣯⣍⢰⠋⠄⠘⠁⠀⠀⠀⠈⠍⠛⠻⢿⣿⣷⣍⡻⣿⣶⣮⣙⠿⢾⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣷⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⠆⣈⠵⠶⠈⢺⡉⠙⠿⣿⣿⣿⣷⡷⠂⠀⠀⠀⠰⣾⡄⢀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⢿⣌⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣍⣽⣿⡜⣆⠳⣯⡲⣤⣀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⡌⡄⠀⠀⠀⠀⠙⢶⣄⠀⠙⢿⣿⣟⣀⠀⠀⠀⠀⠈⢿⣾⡇⠀⠀⠀⣮⢙⣿⣿⣿⣿⣿⣿⣿⣻⣿⣿⣛⣿⣿⣿⣿⣿⣿⣿⣿⡿⠉⢿⡀⠀⠙⢿⣎⢿⣿⣶⣤⣀⠀⠀⠀
⣿⣿⣷⡹⠀⠀⠀⠀⠀⠀⠈⠻⢦⣄⡙⢻⣿⣾⣤⡀⠀⠀⠈⢿⣿⡀⠀⠀⠹⣾⠟⣿⣿⣿⣿⣿⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⠿⡛⠑⠀⠂⠸⡿⠝⠀⠄⢻⣧⢻⣆⠉⡹⠿⣿⡂
⣿⣿⣿⣏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⢻⣿⣿⣿⣿⣷⣄⣀⠈⣿⣷⣄⠀⠘⠙⠰⢿⣿⣿⣿⣿⣿⣿⣧⣚⣿⣿⣯⡋⠄⠰⢉⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣧⢻⣦⠘⡇⠈⠛
⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠈⠉⠙⠛⠛⠻⠾⣿⣿⣟⣷⠀⠀⢪⠙⢿⣿⣿⢿⣿⣿⠙⢻⣿⣿⠁⠶⠔⠈⢑⠋⠀⠀⠀⠀⠀⡀⠀⠀⢿⣿⣧⣙⠦⢻⡀⠀
⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⡆⠀⠘⠷⣷⣧⣽⣾⣯⣿⡗⠸⣿⣿⠀⠠⢰⠚⠊⠀⠂⠀⠀⠀⠀⡌⠈⠒⠘⡿⡁⢹⣶⣾⡇⠀
⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡇⢀⠀⠀⠸⡏⡿⢷⣜⢿⡇⠀⣿⣿⡀⠆⢀⠀⠂⠀⠀⡀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⢿⡿⠁⠀
⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣆⠀⠀⠀⠁⠀⠀⠙⣿⡇⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠈⠂⠀⠐⠁⠀⠀⠀⠀⠀⠀⢸⠅⠀⠀
⣿⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠿⣦⡀⠀⠀⠀⠀⠀⠃⣿⠀⣿⣿⡇⢀⠀⠀⠀⠀⠀⠀⠀⠘⠆⠀⠀⠀⠀⠀⠀⠀⡸⣦⠀⢀
⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣷⡄⠀⣸⣿⡄⠀⡏⠀⢿⢿⡇⠀⠄⠀⠀⠘⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⡄⠀⠀⣿⣿⣿
⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⡀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⡀⠀⠀⠙⡽⢣⡜⠐⠹⠆⠁⠀⢺⣿⡇⠀⠀⠀⠀⠀⠀⢡⡂⠐⠀⠂⢤⡀⠈⠀⠀⠀⢀⣿⣿⣿
*/

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:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   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:67:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   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:92:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   while(sz <= v.size()) sz *= 2;
      |         ~~~^~~~~~~~~~~
rect.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int i=0; i<v.size(); i++) tr[i+sz] = segment2(v[i]);
      |                ~^~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:172:6: warning: unused variable 'ans' [-Wunused-variable]
  172 |  int ans = 0;
      |      ^~~

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