Submission #956690

#	Time	Username	Problem	Language	Result	Execution time	Memory
956690		Macker	Rectangles (IOI19_rect)	C++17	10 / 100	396 ms	285732 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

struct node{
	int on = 0, mxx, mnx, mxy, mny;
};
vector<vector<node>> st;

vector<int> get_last_big(vector<int> v){
	int n = v.size();
	vector<int> res(n, -1);
	stack<pii> s;
	s.push({INT_MAX, -1});
	FOR(i, n){
		int a = v[i];
		while(a >= s.top().ff) s.pop();
		res[i] = s.top().ss;
		s.push({a, i});
	}
	return res;
}

long long count_rectangles(vector<vector<int>> v) {
	int n = v.size();
	int m = v[0].size();
	st.assign(n, vector<node>(m));

	FOR(i, n){
		vector<int> cur;
		vector<int> res;
		FOR(j, m){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(j, m){
			st[i][j].mnx = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, m){
			st[i][j].mxx = m - res[j] - 1;
		}
	}
	FOR(i, m){
		vector<int> cur;
		vector<int> res;
		FOR(j, n){
			cur.push_back(v[j][i]);
		}
		res = get_last_big(cur);
		FOR(j, n){
			st[j][i].mny = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, n){
			st[j][i].mxy = n - res[j] - 1;
		}
	}
	
	vector<vector<pii>> ord(7000005);
	FOR(i, n) FOR(j, m){
		ord[v[i][j]].push_back({i, j});
	}
	ll res = 0;
	for (auto o : ord) {
		for (auto [x, y] : o) {
			st[x][y].on = true;
		}
		for (auto [x, y] : o) {
			int mxx, mnx, mxy, mny;
			mxx = st[x][y].mxx;
			mnx = st[x][y].mnx;
			mxy = st[x][y].mxy;
			mny = st[x][y].mny;
			if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue;

			bool f = 0;
			for (int i = mny + 1; i < mxy; i++){
				for (int j = mnx + 1; j < mxx; j++) {
					if(!st[i][j].on) {f = 1; break;}
					if(st[i][j].mnx < mnx) {f = 1; break;}
					if(st[i][j].mny < mny) {f = 1; break;}
					if(st[i][j].mxx > mxx) {f = 1; break;}
					if(st[i][j].mxy > mxy) {f = 1; break;}
				}
				if(f) break;
			}
			if(!f) res++;
		}
	}
	return res;
}

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