Submission #826893

#	Time	Username	Problem	Language	Result	Execution time	Memory
826893		vjudge1	Rectangles (IOI19_rect)	C++17	25 / 100	5081 ms	84540 KiB

rect

#include <bits/stdc++.h>
#define ll long long
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

using namespace std;

const int maxn=2e5+10;

long long count_rectangles(vector<vector<int> > A)
{
	int n = A.size();
	int m = A[0].size();
	vector <vector <int> > a(n+2), L(n+2), R(n+2), up(n+2), down(n+2);
	forn(0, i, n+1) 
	{
		a[i].assign(m+2, 0);
		up[i].assign(m+2, 0);
		down[i].assign(m+2, 0);
		L[i].assign(m+2, 0);
		R[i].assign(m+2, 0);
	}
	forn(1, i, n)
	{
		forn(1, j, m) a[i][j] = A[i-1][j-1];
	}
	forn(1, i, n)
	{
		stack <int> st;
		forn(1, j, m)
		{
			while(st.size() && a[i][st.top()] < a[i][j])
			{
				st.pop();
			}
			if(st.size())
				L[i][j] = st.top();
			else
				L[i][j] = 0;
			st.push(j);
		}
		while(st.size()) st.pop();
		nfor(1, j, m)
		{
			while(st.size() && a[i][st.top()] < a[i][j])
			{
				st.pop();
			}
			if(st.size())
				R[i][j] = st.top();
			else
				R[i][j] = m+1;
			st.push(j);
		}
	}
	forn(1, j, m)
	{
		stack <int> st;
		forn(1, i, n)
		{
			while(st.size() && a[st.top()][j] < a[i][j])
			{
				st.pop();
			}
			if(st.size())
				up[i][j] = st.top();
			else
				up[i][j] = 0;
			st.push(i);
		}
		while(st.size()) st.pop();
		nfor(1, i, n)
		{
			while(st.size() && a[st.top()][j] < a[i][j])
			{
				st.pop();
			}
			if(st.size())
				down[i][j] = st.top();
			else
				down[i][j] = n+1;
			st.push(i);
		}
	}
	ll ans = 0;
	forn(1, r1, n)
	{
		forn(r1 + 2, r2, n)
		{
			forn(1, c1, m)
			{
				forn(c1 + 2, c2, m)
				{
					int bad = 0;
					forn(c1+1, j, c2-1)
					{
						if(down[r1][j] < r2) bad = 1;
						if(up[r2][j] > r1) bad = 1;
					}
					forn(r1+1, i, r2-1)
					{
						if(R[i][c1] < c2) bad = 1;
						if(L[i][c2] > c1) bad = 1;
					}
					if(!bad)
					{
						ans++;
//						cout << r1 << " " << c1 << " " << r2 << " " << c2 << endl;
					}
				}
			}
		}
	}
	return ans;
}

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