Submission #402019

#	Time	Username	Problem	Language	Result	Execution time	Memory
402019		b00n0rp	Rectangles (IOI19_rect)	C++17	15 / 100	5118 ms	393008 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()
 
const int MX = 2505;
 
int n,m; 
vector<vi> A;
int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX];
vi rows[MX][MX];
vi cols[MX][MX];
 
ll count_rectangles(vector<vi> a) {
	n = a.size();
	m = a[0].size();
	A = a;
	if(n <= 2 or m <= 2) return 0;
	ll ans = 0;
	REP(i,n){
		stack<int> st;
		REP(j,m){
			gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1;
		}
		REP(j,m){
			while(st.size() and a[i][st.top()] <= a[i][j]){
				gr[i][st.top()] = j;
				st.pop();
			}
			st.push(j);
		}
		while(!st.empty()) st.pop();
		FORD(j,m-1,0){
			while(st.size() and a[i][st.top()] <= a[i][j]){
				gl[i][st.top()] = j;
				st.pop();
			}
			st.push(j);
		}
		set<pii> s;
		REP(j,m){
			if(gr[i][j] != -1 and gr[i][j] != j+1) s.insert({j,gr[i][j]});
			if(gl[i][j] != -1 and gl[i][j] != j-1) s.insert({gl[i][j],j});
		}
		for(auto x:s){
			// cout << "row: " << i << " -> " << x.F << " " << x.S << "\n";
			rows[x.F][x.S].pb(i);
		}
	}
	REP(j,m){
		stack<int> st;
		REP(i,n){
			while(st.size() and a[st.top()][j] <= a[i][j]){
				gd[st.top()][j] = i;
				st.pop();
			}
			st.push(i);
		}
		while(!st.empty()) st.pop();
		FORD(i,n-1,0){
			while(st.size() and a[st.top()][j] <= a[i][j]){
				gu[st.top()][j] = i;
				st.pop();
			}
			st.push(i);
		}
		set<pii> s;
		REP(i,n){
			if(gd[i][j] != -1 and gd[i][j] != i+1) s.insert({i,gd[i][j]});
			if(gu[i][j] != -1 and gu[i][j] != i-1) s.insert({gu[i][j],i});
		}
		for(auto x:s){
			cols[x.F][x.S].pb(j);
			// cout << "col: " << j << " -> " << x.F << " " << x.S << "\n";
		}
	}
	FOR(c1,1,n-1){
		FOR(c2,c1,n-1){
			FOR(r1,1,m-1){
				FOR(r2,r1,m-1){
					bool flag = true;
					FOR(i,c1,c2+1){
						flag &= binary_search(all(rows[r1-1][r2+1]),i);
					}
					FOR(i,r1,r2+1){
						flag &= binary_search(all(cols[c1-1][c2+1]),i);
					}
					if(flag){
						ans++;
						// cout << c1 << " " << c2 << " " << r1 << " " << r2 << "\n";
					}
				}
			}
		}
	}
	return ans;
}

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