Submission #836141

#	Time	Username	Problem	Language	Result	Execution time	Memory
836141		penguinman	Rectangles (IOI19_rect)	C++17	37 / 100	5066 ms	112892 KiB

rect

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

#ifndef EVAL
#include "grader.cpp"
#endif

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];*/


struct binary_indexed_tree{
	vi node;
	ll N;
	binary_indexed_tree(int n): N(n){
		node.resize(N+1);
	}
	void add(ll idx, ll val){
		idx++;
		for(; idx<=N; idx+=(idx&-idx)) node[idx] += val;
	}
	ll sum(ll idx){
		idx++;
		ll ret = 0;
		for(; 0<idx; idx-=(idx&-idx)) ret += node[idx];
		return ret;
	}
};

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(H);
			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]);
			}
			binary_indexed_tree bit(H);
			vii mem(H+1);
			ll last = 0;
			rep(l,1,H-1){
				mem[down_state[l-1]].pb(l);
				for(auto el: mem[l]) bit.add(el, -1);
				bit.add(l,1);
				if(right[l][j-1] <= k || left[l][k+1] >= j){
					last = l;
				}
				else{
					ll b = std::max(last, up_state[l+1]);
					ans += bit.sum(l)-bit.sum(b);
				}
			}
		}
	}
	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