Submission #1049068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049068		Kel_Mahmut	Rectangles (IOI19_rect)	C++14	72 / 100	2198 ms	1048576 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;

	
	auto compute = [&](int N, int M, vector<vector<int>> &aa){
		vector<vector<pair<int, int>>> arr(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({aa[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)
						arr[i].pb({tl, tr});
			}
		}
		return arr;
	};

	auto extend = [&](int N, int M, vector<vector<pair<int, int>>> & ROWS, int t){
		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((t ? make_pair(cev, tr) : make_pair(tr, cev)));
				dp[tl][tr] = i;
				dp2[tl][tr] = cev;
			}
		}
		vector<vector<vector<pair<int, int>>>> ret(M, vector<vector<pair<int, int>>>(N));
		for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) ret[j][i] = down_extend[i][j];
		return (t ? ret : down_extend);
	};

	vector<vector<int>> A(m, vector<int>(n));
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) A[j][i] = a[i][j];
	auto rows = compute(n, m, a);
	auto cols = compute(m, n, A);
	auto down_extend = extend(n, m, rows, 0);
	auto right_extend = extend(m, n, cols, 1);

	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;
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for(auto [tl, tr] : interval)
      |              ^
rect.cpp: In lambda function:
rect.cpp:101:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |    for(auto [tl, tr] : ROWS[i]){
      |             ^
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:129:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |    for(auto [tr, ext] : down_extend[i][j]){
      |             ^

• 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