Submission #596359

#	Time	Username	Problem	Language	Result	Execution time	Memory
596359		AriaH	Rectangles (IOI19_rect)	C++17	100 / 100	2698 ms	736316 KiB

rect

#include "rect.h"
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 2510;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;

vector < pii > R[N][N], D[N][N];

ll tot;

ll count_rectangles(vector < vector < int > > A)
{
	int n = SZ(A), m = SZ(A[0]);
	///printf("n = %d m = %d\n", n, m);
	for(int i = 0; i < n; i ++)
	{
		vector < int > vec;
		for(int j = 0; j < m; j ++)
		{
			while(SZ(vec) && A[i][j] > A[i][vec.back()])
			{
				if(j - vec.back() > 1) R[i][vec.back() + 1].push_back({j - 1, i});
				vec.pop_back();
			}
			if(SZ(vec))
			{
				if(j - vec.back() > 1) R[i][vec.back() + 1].push_back({j - 1, i});
				if(A[i][vec.back()] == A[i][j]) vec.pop_back();		
			}
			vec.push_back(j);
		}
	}
	for(int j = 0; j < m; j ++)
	{
		vector < int > vec;
		for(int i = 0; i < n; i ++)
		{
			while(SZ(vec) && A[i][j] > A[vec.back()][j])
			{
				if(i - vec.back() > 1) D[vec.back() + 1][j].push_back({i - 1, j});
				vec.pop_back();
			}
			if(SZ(vec))
			{
				if(i - vec.back() > 1) D[vec.back() + 1][j].push_back({i - 1, j});
				if(A[i][j] == A[vec.back()][j]) vec.pop_back();
			}
			vec.push_back(i);
		}
	}
	for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) { sort(all(R[i][j])), sort(all(D[i][j])); }
	for(int i = n - 1; ~i; i --)
	{
		for(int j = m - 1; ~j; j --)
		{
			for(int t = 0; t < SZ(R[i][j]); t ++)
			{
				int id = lower_bound(all(R[i + 1][j]), R[i][j][t]) - R[i + 1][j].begin();
				if(id < SZ(R[i + 1][j]) && R[i + 1][j][id].F == R[i][j][t].F)
				{
					R[i][j][t].S = R[i + 1][j][id].S;
				}
			}
			for(int t = 0; t < SZ(D[i][j]); t ++)
			{
				int id = lower_bound(all(D[i][j + 1]), D[i][j][t]) - D[i][j + 1].begin();
				if(id < SZ(D[i][j + 1]) && D[i][j + 1][id].F == D[i][j][t].F)
				{
					D[i][j][t].S = D[i][j + 1][id].S;
				}
			}
		}
	}
	for(int i = 0; i < n; i ++)
	{
		for(int j = 0; j < m; j ++)
		{
			for(auto [a, b] : R[i][j])
			{
				for(auto [c, d] : D[i][j])
				{
					tot += (a <= d && c <= b);
				}
			}
		}
	}
	return tot;
}

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