Submission #824999

#	Time	Username	Problem	Language	Result	Execution time	Memory
824999		Ronin13	Rectangles (IOI19_rect)	C++17	72 / 100	5139 ms	805872 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 st[nmax][nmax][13][2];

int get_max(int ind, int l, int r){
	int len = r - l + 1;
	int x = log2(len);
	return max(st[ind][l][x][0], st[ind][max(0,r - (1 << x) + 1)][x][0]);
}

int get_mn(int ind, int l, int r){
	int len = r - l + 1;
	int x = log2(len);
	return min(st[ind][l][x][1], st[ind][max(0, r - (1 << x) + 1)][x][1]);
}

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++){
		for(int j = n - 1; j >= 0; j--){
			st[i][j][0][0] = d[j][i], st[i][j][0][1] = c[j][i];
			for(int x =1; x < 13; x++){
				st[i][j][x][0] = max(st[i][j][x - 1][0], 
									st[i][min(j + (1 << (x - 1)), n - 1)][x - 1][0]);
				st[i][j][x][1] = min(st[i][j][x - 1][1], 
									st[i][min(j + (1 << (x - 1)), n - 1)][x - 1][1]);
			}
		}
	}
	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];
		vector <pii> nw;
		for(int j = i; j < m - 1; j++){
			
			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);
			nw.clear();
			for(auto to : cur){
				//if(i == 3 && j == 3) cout << to.f << ' ' << to.s << "\n";
				int L = to.f, R = to.s;
				if(get_max(j + 1, L, R) >= i) continue;
			//	if(i == 3 && j == 3) cout << to.f << ' ' << to.s << "\n";
			//	cout << get_mn(i - 1, L, R) << "\n";
				if(get_mn(i - 1, L, R) <= 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:106: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]
  106 |    while(inda < cur.size() && indb < p[j].size()){
      |          ~~~~~^~~~~~~~~~~~
rect.cpp:106: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]
  106 |    while(inda < cur.size() && indb < p[j].size()){
      |                               ~~~~~^~~~~~~~~~~~~

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