Submission #826923

#	Time	Username	Problem	Language	Result	Execution time	Memory
826923		vjudge1	Rectangles (IOI19_rect)	C++17	0 / 100	1 ms	724 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;

int n, m, fen[maxn];

void updfen(int r, int val)
{
	for(; r <= m; r = ((r + 1) | r)) fen[r] += val;
}

int getfen(int r)
{
	int ret = 0;
	for(; r >= 0; r = ((r+1)&r)-1) ret += fen[r];
	return ret;
}

long long count_rectangles(vector<vector<int> > A)
{
	n = A.size();
	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;
	vector <int> R2(m+2, 0), L2(m+2, 0);
	vector <vector <int> > start;
	start.assign(m+2, {});
	forn(1, r1, n)
	{
		forn(1, c, m)
		{
			R2[c] = R[r1+1][c];
			L2[c] = L[r1+1][c];
		}
		forn(r1+2, r2, n)
		{
			int latest_bad = m;
			forn(1, c1, m)
			{
				fen[c1] = 0;
				start[c1].clear();
			}
			nfor(1, c1, m)
			{
				if(min(R2[c1], latest_bad) >= c1+2)
					ans += getfen(min(R2[c1], latest_bad));
//				if(getfen(min(R2[c1], latest_bad)))
//					cout << r1 << " " << r2 << " " << c1 << " " << getfen(min(R2[c1], latest_bad)) << " " << latest_bad << " " << R2[c1] << endl;
				start[L2[c1]].pb(c1);
				updfen(c1, 1);
				for(auto i : start[c1])
				{
					updfen(i, -1);
				}
				if(up[r2][c1] < r1 || down[r1][c1] > r2) latest_bad = c1;
			}
			forn(1, c1, m)
			{
				L2[c1] = max(L2[c1], L[r2][c1]);
				R2[c1] = min(R2[c1], R[r2][c1]);
			}
		}
	}
	return ans;
}

• 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