제출 #906264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906264		vjudge1	Rectangles (IOI19_rect)	C++17	0 / 100	4 ms	1628 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;



long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = sz(a);
	int m = sz(a[0]);
	vector<vector<map<int,int>>> rowf(n,vector<map<int,int>>(m));
	rep(i,0,n){
		vector<pii> stack;
		rep(j,0,m){
			
			while(sz(stack) && stack.back().F < a[i][j]){
				if(stack.back().S+1 <= j-1) rowf[i][stack.back().S+1][j-1]=-1;
				stack.pop_back();
			}
			if(sz(stack) && stack.back().S+1 <= j-1) rowf[i][stack.back().S+1][j-1]=-1;
			stack.pb({a[i][j],j});
		}
	}

	vector<vector<map<int,int>>> colf(n,vector<map<int,int>>(m));
	rep(j,0,m){
		vector<pii> stack;
		rep(i,0,n){
			while(sz(stack) && stack.back().F < a[i][j]){
				if(stack.back().S+1<=i-1) colf[stack.back().S+1][j][i-1]=-1;
				stack.pop_back();
			}
			if(sz(stack) && stack.back().S+1<=i-1) colf[stack.back().S+1][j][i-1]=-1;
			stack.pb({a[i][j],i});
		}
	}

	
	rep(i,0,n)rep(j,0,m){
		for(auto p : rowf[i][j]){
			if(p.S == -1){
				int k = i;
				while(k<n && rowf[k][j].count(p.F)) k++;
				rep(l,i,k) rowf[l][j][p.F]=k-1;
			}
		}
		for(auto p : colf[i][j]){
			if(p.S == -1){
				int k = j;
				while(k<m && colf[i][k].count(p.F)) k++;
				rep(l,j,k) colf[i][l][p.F]=k-1;
			}
		}
	}

	// rep(i,0,n){
	// 	rep(j,0,m){
	// 		cout<<i<<' '<<j<<" rows:";
	// 		for(pii x : rowf[i][j]) cout<<' '<<x.F<<","<<x.S;
	// 		cout<<endl;
	// 		cout<<i<<' '<<j<<" cols:";
	// 		for(pii x : colf[i][j]) cout<<' '<<x.F<<","<<x.S;
	// 		cout<<endl;
	// 	}
	// }

	ll ans = 0;
	rep(i,0,n){
		rep(j,0,m){
			for(pii l : colf[i][j])for(pii r : rowf[i][j]){
				// [i, r.F], r.S tells how far we go on other
				// [j, l.F], l.S tells how far we go on other
				bool good = l.S>=r.F && r.S >= l.F;
				// cout<<i<<' '<<j<<" ("<<l.F<<','<<l.S<<") ("<<r.F<<','<<r.S<<") "<<good<<endl;
				ans += good;
			}
		}
	}

	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