Submission #824955

#	Time	Username	Problem	Language	Result	Execution time	Memory
824955		Ronin13	Rectangles (IOI19_rect)	C++17	50 / 100	5029 ms	234592 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);
	}
	vector <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].pb({l[i] + 1, r[i] - 1});
		}
		sort(p[j].begin(), p[j].end());
		p[j].erase(unique(p[j].begin(), p[j].end()), p[j].end());
	}
	int ans = 0;
	for(int i = 1; i < m - 1; i++){
		vector <pii> cur = p[i];
		for(int j = i; j < m - 1; j++){
			vector <pii> nw;
			int inda = 0, indb = 0;
			while(inda < cur.size() && indb < p[j].size()){
				if(cur[inda] == p[j][indb]) nw.pb(cur[inda]), inda++, indb++;
				else{
					if(cur[inda] < p[j][indb]) inda++;
					else indb++;
				}
			}
			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;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    while(inda < cur.size() && indb < p[j].size()){
      |          ~~~~~^~~~~~~~~~~~
rect.cpp:119:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    while(inda < cur.size() && indb < p[j].size()){
      |                               ~~~~~^~~~~~~~~~~~~

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