Submission #836040

#	Time	Username	Problem	Language	Result	Execution time	Memory
836040		penguinman	Rectangles (IOI19_rect)	C++17	0 / 100	5033 ms	114584 KiB

rect

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

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple

constexpr ll inf = (1ll<<60);
/*
constexpr ll LOG = 12;
ll left_table[2510][2510][LOG+1];
ll right_table[2510][2510][LOG+1];
ll up_table[2510][2510][LOG+1];
ll down_table[2510][2510][LOG+1];*/

long long count_rectangles(std::vector<std::vector<int> > a) {
	ll H = a.size(), W = a[0].size();
	vii left(H,vi(W)), right(H,vi(W)), down(H,vi(W)), up(H,vi(W));
	ll ans = 0;
	{
		rep(i,0,H){
			std::deque<ll> max, idx;
			max.pb(inf);
			idx.pb(-1);
			rep(j,0,W){
				while(max[0] < a[i][j]){
					max.pop_front();
					idx.pop_front();
				}
				left[i][j] = idx[0];
				max.emplace_front(a[i][j]);
				idx.emplace_front(j);
			}
		}
	}
	{
		rep(i,0,H){
			std::deque<ll> max, idx;
			max.pb(inf);
			idx.pb(W);
			per(j,W-1,0){
				while(max[0] < a[i][j]){
					max.pop_front();
					idx.pop_front();
				}
				right[i][j] = idx[0];
				max.emplace_front(a[i][j]);
				idx.emplace_front(j);

			}
		}
	}
	{
		rep(j,0,W){
			std::deque<ll> max, idx;
			max.pb(inf);
			idx.pb(-1);
			rep(i,0,H){
				while(max[0] < a[i][j]){
					max.pop_front();
					idx.pop_front();
				}
				up[i][j] = idx[0];
				max.emplace_front(a[i][j]);
				idx.emplace_front(i);
			}
		}
	}
	{
		rep(j,0,W){
			std::deque<ll> max, idx;
			max.pb(inf);
			idx.pb(-1);
			per(i,H-1,0){
				while(max[0] < a[i][j]){
					max.pop_front();
					idx.pop_front();
				}
				down[i][j] = idx[0];
				max.emplace_front(a[i][j]);
				idx.emplace_front(i);
			}
		}
	}

	rep(j,1,W-1){
		vi up_state(H,-inf);
		vi down_state(H,inf);
		rep(k,j,W-1){
			rep(i,0,H){
				up_state[i] = std::max(up_state[i], up[i][k]);
				down_state[i] = std::min(down_state[i], down[i][k]);
			}
			rep(l,1,H-1){
				rep(r,l,H-1){
					if(right[r][j-1] <= k) break;
					if(left[r][k+1] >= j) break;
					if(up_state[r+1] < l && down_state[l-1] > r) ans++;
				}
			}
		}
	}
	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