Submission #1049257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049257		efedmrlr	Rectangles (IOI19_rect)	C++17	72 / 100	5074 ms	574716 KiB

rect

#include "rect.h"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n, m;

struct DSU {
	vector<int> p, sz;
	vector<int> l, r;
	vector<int> used;
	int mx;
	void reset(int s, int mm) {
		p.assign(s + 3, -1);
		sz.assign(s + 3, 0);
		l.assign(s + 3, INF);
		r.assign(s + 3, 0);
		used.assign(s + 3, -1);
		mx = mm;
	}
	void make_set(int x)  {
		p[x] = x;
		sz[x] = 1;
		l[x] = r[x] = x;
	}
	int find_set(int x) {
		return p[x] == x ? x : find_set(p[x]);
 	}
	void union_set(int x, int y) {
		x = find_set(x); y = find_set(y);
		if(x == y) return;
		if(sz[x] < sz[y]) swap(x, y);
		sz[x] += sz[y];
		p[y] = x;
		l[x] = min(l[x], l[y]);
		r[x] = max(r[x], r[y]);	
	}
	bool check_val(int x) {
		return !(l[x] == 0 || r[x] == mx);
	}

};
long long count_rectangles(std::vector<std::vector<int> > a) {
	n = (int)a.size();
	m = (int)a[0].size();
	vector<vector<array<int, 3 > > > row(n), col(m);
	REP(i, n - 1) {
		if(i == 0) continue;
		DSU ds;
		ds.reset(m, m - 1);
		vector<int> ord;
		REP(j, m) ord.pb(j);
		sort(all(ord), [&](int x, int y) {
			return a[i][x] < a[i][y];
		});
		int last = -1, lind = 0;
		for(int k = 0; k  < ord.size(); k++) {
			auto &c = ord[k];
			if(a[i][c] != last) {
				for(int j = lind; j < k; j++) {
					if(ds.used[ds.find_set(ord[j])] == lind) {
						continue;
					} 
					ds.used[ds.find_set(ord[j])] = lind;
					if(!ds.check_val(ds.find_set(ord[j]))) continue;
					row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])]});
				}
				
				last = a[i][c];
				lind = k;
			}
			ds.make_set(c);
			if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
			if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
		}
		for(int j = lind; j < ord.size(); j++) {
			if(ds.used[ds.find_set(ord[j])] == lind) {
				continue;
			} 
			ds.used[ds.find_set(ord[j])] = lind;
			if(!ds.check_val(ds.find_set(ord[j]))) continue;
				row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])], 0});
			}
	}
	REP(j, m - 1) {
		if(j == 0) continue;
		DSU ds;
		ds.reset(n, n - 1);
		vector<int> ord;
		REP(i, n) ord.pb(i);
		sort(all(ord), [&](int x, int y) {
			return a[x][j] < a[y][j];
		});
		int last = -1, lind = 0;
		for(int k = 0; k < ord.size(); k++) {
			auto &c = ord[k];
			if(a[c][j] != last) {
				for(int i = lind; i < k; i++) {
					if(ds.used[ds.find_set(ord[i])] == lind) {
						continue;
					} 
					ds.used[ds.find_set(ord[i])] = lind;
					if(!ds.check_val(ds.find_set(ord[i]))) continue;
					col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])]});
				}
				
				last = a[c][j];
				lind = k;
			}
			ds.make_set(c);
			if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
			if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
		}
		for(int i = lind; i < ord.size(); i++) {
			if(ds.used[ds.find_set(ord[i])] == lind) {
				continue;
			} 
			ds.used[ds.find_set(ord[i])] = lind;
			if(!ds.check_val(ds.find_set(ord[i]))) continue;
				col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])], 0});
		}
	}
	// cout << "rows: \n";
	// for(int i = 0; i < n; i++) {
	// 	cout << "i:" << i << "\n";
	// 	for(auto c : row[i]) {
	// 		cout << c[0] << " " << c[1] << "\n";
	// 	}
	// } 

	map<array<int, 3>, int > mpp;
	for(int i = n - 1; i >= 0; i--) {
		for(auto &c : row[i]) {
			mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1;
		}
	}
	mpp.clear();
	for(int i = m - 1; i >= 0; i--) {
		for(auto &c : col[i]) {
			mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1;
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(auto &c : row[i]) {
			for(auto cl : col[c[0]]) {
				if(cl[0] != i) continue;
				if(cl[1] - cl[0] + 1 <= c[2] && c[1] - c[0] + 1 <= cl[2]) {
					ans++;
				} 
			}
		}
	}

	return ans;
}

// int main() {
// 	int n, m;
// 	cin >> n >> m;
// 	vector<vector<int> > grid(n,vector<int>(m));
// 	REP(i, n) REP(j, m) {
// 		cin >> grid[i][j];
// 	}
// 	cout << count_rectangles(grid) << "\n";
// 	return 0;
// }

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int k = 0; k  < ord.size(); k++) {
      |                  ~~~^~~~~~~~~~~~
rect.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int j = lind; j < ord.size(); j++) {
      |                     ~~^~~~~~~~~~~~
rect.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(int k = 0; k < ord.size(); k++) {
      |                  ~~^~~~~~~~~~~~
rect.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int i = lind; i < ord.size(); i++) {
      |                     ~~^~~~~~~~~~~~

• 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