제출 #836322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836322		penguinman	Rectangles (IOI19_rect)	C++17	72 / 100	5040 ms	407064 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 = int;
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
#define ln "\n"

constexpr ll inf = (1ll<<30);
/*
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();
	long long ans = 0;
	vector<vector<vector<pii>>> query(H,vector<vector<pii>>(W));
	{
		vector<std::map<ll,ll>> dp_right(W);
        vector<std::map<ll,ll>> right(W);
		per(i,H-1,0){
			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();
				}
				if(idx[0] != -1) right[idx[0]][j] = 1;
				max.emplace_front(a[i][j]);
				idx.emplace_front(j);
			}
			max.clear();
			idx.clear();
			max.pb(inf);
			idx.pb(W);
			per(j,W-1,0){
				while(max[0] < a[i][j]){
					max.pop_front();
					idx.pop_front();
				}
				if(idx[0] != W) right[j][idx[0]] = 1;
				max.emplace_front(a[i][j]);
				idx.emplace_front(j);
			}

			rep(j,0,W){
				if(right[j].count(j+1)) right[j].erase(j+1);
				for(auto &el: right[j]){
					if(dp_right[j].count(el.first)) el.second += dp_right[j][el.first];
				}
			}

			rep(j,1,W-1){
				for(auto el: right[j-1]){
					ll bottom = i+el.second;
					// bottom 以下 かつ
					ll lasting = el.first-j;
					// lasting 以上
					query[i][j].pb(mp(lasting, -bottom));
				}
			}

            rep(j,0,W){
                dp_right[j] = right[j];
                right[j].clear();
            }

		}
	}
	{
		vector<std::map<ll,ll>> dp_down(H);
        vector<std::map<ll,ll>> down(H);
		per(j,W-1,0){
			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();
				}
				if(idx[0] != -1) down[idx[0]][i] = 1;
				max.emplace_front(a[i][j]);
				idx.emplace_front(i);
			}
			max.clear();
			idx.clear();
			max.pb(inf);
			idx.pb(H);
			per(i,H-1,0){
				while(max[0] < a[i][j]){
					max.pop_front();
					idx.pop_front();
				}
				if(idx[0] != H) down[i][idx[0]] = 1;
				max.emplace_front(a[i][j]);
				idx.emplace_front(i);
			}

			rep(i,0,H){
				if(down[i].count(i+1)) down[i].erase(i+1);
				for(auto &el: down[i]){
					if(dp_down[i].count(el.first)) el.second += dp_down[i][el.first];
				}
			}

			rep(i,1,H-1){
				for(auto el: down[i-1]){
					query[i][j].pb(mp(el.second, el.first));
				}
			}

            rep(i,0,H){
                dp_down[i] = down[i];
                down[i].clear();
            }
		}
	}

	binary_indexed_tree bit(H+10);
	rep(i,1,H-1){
		rep(j,1,W-1){
			auto query_ = query[i][j];
			sort(all(query_));
			reverse(all(query_));
			for(auto el: query_){
				if(el.second < 0) ans += bit.sum(-el.second);
				else bit.add(el.second,1);
			}
			for(auto el: query_){
				if(el.second > 0) bit.add(el.second,-1);
			}
		}
	}
	return ans;
}

• 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