제출 #836381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836381		penguinman	Rectangles (IOI19_rect)	C++17	100 / 100	3676 ms	461140 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));
	{
        vii dp_right(W,vi(W));
        vii right(W,vi(W));
        vii rem(W);
        vii new_rem(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;
                    new_rem[idx[0]].pb(j);
                }
				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 && a[i][j] != max[0]){
                    right[j][idx[0]] = 1;
                    new_rem[j].pb(idx[0]);
                }
				max.emplace_front(a[i][j]);
				idx.emplace_front(j);
			}

			rep(j,0,W){
                if(j+1 < W) right[j][j+1] = 0;
				for(auto el: new_rem[j]){
                    if(el == j+1) continue;
                    right[j][el] += dp_right[j][el];
				}
			}

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

            rep(j,0,W){
                for(auto el: rem[j]) dp_right[j][el] = 0;
                for(auto el: new_rem[j]){
                    dp_right[j][el] = right[j][el];
                    right[j][el] = 0;
                }
                rem[j] = new_rem[j];
                new_rem[j].clear();
            }

		}
	}
	{
        vii dp_down(H,vi(H));
        vii down(H,vi(H));
        vii rem(H);
        vii new_rem(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;
                    new_rem[idx[0]].pb(i);
                }
				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 && a[i][j] != max[0]){
                    down[i][idx[0]] = 1;
                    new_rem[i].pb(idx[0]);
                }
				max.emplace_front(a[i][j]);
				idx.emplace_front(i);
			}

			rep(i,0,H){
                if(i+1 < H) down[i][i+1] = 0;

				for(auto el: new_rem[i]){
                    if(el == i+1) continue;
                    down[i][el] += dp_down[i][el];
				}
			}

			rep(i,1,H-1){
				for(auto el: new_rem[i-1]){
                    if(el == i) continue;
					query[i][j].pb(mp(down[i-1][el], el));
				}
			}

            rep(i,0,H){
                for(auto el: rem[i]) dp_down[i][el] = 0;
                for(auto el: new_rem[i]){
                    dp_down[i][el] = down[i][el];
                    down[i][el] = 0;
                }
                rem[i] = new_rem[i];
                new_rem[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: 28 / 28