Submission #1048816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048816		vjudge1	Rectangles (IOI19_rect)	C++17	100 / 100	4176 ms	974228 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct DSU{
	int n, t;
	vector<int> p;
	DSU(int n, int t) : n(n), t(t), p(n) {
		for(int i = 0; i < n; i++) p[i] = i;
	}

	int find(int u){
		if(p[u] == u) return u;
		return p[u] = find(p[u]);
	}

	void merge(int u, int v){
		u = find(u);
		v = find(v);
		if(u == v) return;
		if(u > v) swap(u, v);
		if(t)
			p[u] = v;
		else
			p[v] = u;
	}
};

struct fenwick{
	int n;
	vector<int> fen;
	fenwick(int n) : n(n), fen(n){}

	void upd(int pos, int val){
		for(; pos < n; pos |= pos + 1)
			fen[pos] += val;
	}

	int query(int pos){
		int ret = 0;
		for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
			ret += fen[pos];
		return ret;
	}

	int query(int ql, int qr){
		return query(qr) - query(ql - 1);
	}

};

ll count_rectangles(vector<vector<int>> a){
	int n = a.size(), m = a[0].size();
	ll ans = 0;

	vector<vector<pair<int, int>>> rows(n);
	for(int i = 0; i < n; i++){
		vector<pair<int, int>> vals;
		vector<int> act(m);
		DSU left(m, 0), right(m, 1);
		for(int j = 0; j < m; j++)
			vals.pb({a[i][j], j});
		sort(all(vals));
		vector<vector<int>> same_idx(m);
		int c = -1;
		for(int k = 0, lst = -1; k < m; k++){
			c += (lst != vals[k].first);
			same_idx[c].pb(vals[k].second);
			lst = vals[k].first;
		}
		same_idx.resize(c);

		for(int j = 0; j < c; j++){
			for(int ind : same_idx[j]){
				act[ind] = 1;
				if(ind && act[ind - 1])
					left.merge(ind - 1, ind), right.merge(ind - 1, ind);
				if(ind < m - 1 && act[ind + 1])
					left.merge(ind, ind + 1), right.merge(ind, ind + 1);
			}
			set<pair<int, int>> interval;
			for(int ind : same_idx[j])
				interval.insert({left.find(ind), right.find(ind)});
			for(auto [tl, tr] : interval)
				if(tl != 0 && tr != m - 1)
					rows[i].pb({tl, tr});
		}
	}

	vector<vector<vector<pair<int, int>>>> down_extend(n, vector<vector<pair<int, int>>>(m));
	vector<vector<int>> dp(m, vector<int>(m, -1));
	vector<vector<int>> dp2(m, vector<int>(m, -1));
	for(int i = n - 1; i >= 0; i--){
		for(auto [tl, tr] : rows[i]){
			int cev = (dp[tl][tr] == i + 1 ? dp2[tl][tr] + 1 : 1);
			down_extend[i][tl].pb({tr, cev});
			dp[tl][tr] = i;
			dp2[tl][tr] = cev;
		}
	}

	vector<vector<pair<int, int>>> cols(m);
	for(int i = 0; i < m; i++){
		vector<pair<int, int>> vals;
		vector<int> act(n);
		DSU up(n, 0), down(n, 1);
		for(int j = 0; j < n; j++)
			vals.pb({a[j][i], j});
		sort(all(vals));
		vector<vector<int>> same_idx(n);
		int c = -1;
		for(int k = 0, lst = - 1; k < n; k++){
			c += (vals[k].first != lst);
			same_idx[c].pb(vals[k].second);
			lst = vals[k].first;
		}
		same_idx.resize(c);

		for(int j = 0; j < c; j++){
			for(int ind : same_idx[j]){
				act[ind] = 1;
				if(ind && act[ind - 1])
					up.merge(ind - 1, ind), down.merge(ind - 1, ind);
				if(ind < n - 1 && act[ind + 1])
					up.merge(ind, ind + 1), down.merge(ind, ind + 1);
			}
			set<pair<int, int>> interval;
			for(int ind : same_idx[j])
				interval.insert({up.find(ind), down.find(ind)});
			for(auto [tl, tr] : interval)
				if(tl != 0 && tr != n - 1)
					cols[i].pb({tl, tr});
		}
	}

	vector<vector<vector<pair<int, int>>>> right_extend(n, vector<vector<pair<int, int>>>(m));
	vector<vector<int>> DP(n, vector<int>(n));
	vector<vector<int>> DP2(n, vector<int>(n));
	for(int i = m - 1; i >= 0; i--){
		for(auto [tl, tr] : cols[i]){
			int cev = (DP[tl][tr] == i + 1 ? DP2[tl][tr] + 1 : 1);
			right_extend[tl][i].pb({cev, tr});
			DP[tl][tr] = i;
			DP2[tl][tr] = cev;
		}
	}

	fenwick fen(n);
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
			sort(all(right_extend[i][j]));
			sort(all(down_extend[i][j])); reverse(all(down_extend[i][j]));
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			int c = right_extend[i][j].size() - 1;
			vector<int> rollback;
			for(auto [tr, ext] : down_extend[i][j]){
				while(c >= 0 && j + right_extend[i][j][c].first - 1 >= tr){
					fen.upd(right_extend[i][j][c].second , 1);
					rollback.pb(right_extend[i][j][c].second);
					c--;
				}
				ans += fen.query(i, i + ext - 1);
			}
			for(int x : rollback)
				fen.upd(x, -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