Submission #824946

#	Time	Username	Problem	Language	Result	Execution time	Memory
824946		Ronin13	Rectangles (IOI19_rect)	C++17	37 / 100	5049 ms	130280 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back 
#define epb emplace_back
using namespace std;
const int nmax = 2501;

int c[nmax][nmax];// for min
int d[nmax][nmax];// for max

int t[4 * nmax][nmax];
int T[4 * nmax][nmax];

void build(int v, int l, int r, int ind){
	if(l == r){
		t[v][ind] = c[l][ind];
		T[v][ind] = d[l][ind];
		return;
	}
	int m = (l + r) / 2;
	build(2 * v, l, m, ind);
	build(2 * v + 1, m + 1, r, ind);
	t[v][ind] = min(t[v * 2][ind], t[2 * v+ 1][ind]);
	T[v][ind] = max(T[v * 2][ind], T[v * 2 + 1][ind]);
}


int get_max(int v, int l, int r, int st, int fin, int ind){
	if(l > fin || r < st) return 0;
	if(l >= st && r <= fin){
		return T[v][ind];
	}
	int m =(l + r) / 2;
	return max(get_max(2 * v, l, m, st, fin, ind),
				get_max(2 * v + 1, m + 1, r, st, fin, ind));
}

int get_min(int v, int l, int r, int st, int fin, int ind){
	if(l > fin || r < st) return 1e9;
	if(l >= st && r <= fin){
		return t[v][ind];
	}
	int m =(l + r) / 2;
	return min(get_min(2 * v, l, m, st, fin, ind),
				get_min(2 * v + 1, m + 1, r, st, fin, ind));
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	for(int i = 0; i < n; i++){
		stack <int> st;
		for(int j = 0; j < m; j++){
			while(!st.empty()){
				if(a[i][st.top()] < a[i][j]) st.pop();
				else break;
			}
			if(!st.empty())
			d[i][j] = st.top();
			st.push(j);
		}
		while(!st.empty()){
			st.pop();
		}
		for(int j= m - 1 ;j >= 0; j--){
			while(!st.empty()){
				if(a[i][st.top()] < a[i][j]) st.pop();
				else break;
			}
			if(!st.empty()) c[i][j] = st.top();
			else c[i][j] = m - 1;
			st.push(j);
		}
	}
	for(int i = 0; i < m; i++){
		build(1, 0, n - 1, i);
	}
	set <pii> p[m + 1];
	for(int j = 0; j < m; j++){
		int l[n + 1], r[n + 1];
		fill(l , l + n + 1, -1);
		fill(r, r + n + 1, n + 1);
		stack <int> st;
		for(int i = 0; i < n; i++){
			while(!st.empty()){
				if(a[st.top()][j] > a[i][j]) break;
				else st.pop();
			}
			if(!st.empty()) l[i] = st.top();
			st.push(i);
		}
		while(!st.empty()) st.pop();
		for(int i = n - 1; i >= 0; i--){
			while(!st.empty()){
				if(a[st.top()][j] > a[i][j]) break;
				else st.pop();
			}
			if(!st.empty()) r[i] = st.top();
			st.push(i);
		}
		for(int i = 0; i < n; i++){
			if(l[i] != -1  && r[i] != n + 1)
				p[j].insert({l[i] + 1, r[i] - 1});
		}
	}
	int ans = 0;
	for(int i = 1; i < m - 1; i++){
		set <pii> cur = p[i];
		for(int j = i; j < m - 1; j++){
			set <pii> nw;
			for(auto to : p[j]) if(cur.find(to) != cur.end()) nw.insert(to);
			swap(nw, cur);
			for(auto to : cur){
				int L = to.f, R = to.s;
				if(get_max(1, 0, n - 1, L, R, j + 1) >= i) continue;
				if(get_min(1, 0, n - 1, L, R, i - 1) <= j) continue;
				//cout << i << ' ' << j << ' ' << L << ' ' << R << "\n";
				ans++;
			}
		}
	}
	return ans;
}

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