Submission #1049285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049285		efedmrlr	Rectangles (IOI19_rect)	C++17	72 / 100	5032 ms	1016992 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);
	}

};

struct Fenwick {
	vector<int> data;
	int sz;
	void reset(int s) {
		sz = s;
		data.assign(sz + 3, 0);
	}
	void update(int ind, int val) {
		ind++;
		while(ind <= sz) {
			data[ind] += val;
			ind += (-ind) & ind;
		}
	} 
	int getSum(int ind) {
		ind++;
		int ret = 0;
		while(ind > 0) {
			ret += data[ind];
			ind -= ind & (-ind);
		}
		return ret;
	}
	int query(int l, int r) {
		return getSum(r) - (l > 0 ? getSum(l - 1) : 0);
	} 
};

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;
		}
	}
	
	vector<vector<vector<array<int, 2> > > > rows(n, vector<vector<array<int, 2> > >(m)), cols(n, vector<vector<array<int, 2> > >(m));
	for(int i = 0; i < n; i++) {
		for(auto c : row[i]) {
			rows[i][c[0]].pb({c[1] - c[0] + 1, c[2]});
		}
		for(int j = 0; j < m; j++) {
			sort(all(rows[i][j]), [&](array<int, 2> x, array<int, 2> y) {
				return x[1] < y[1];
			});
		}
	}
	// cout << "zort" << endl;
	for(int j = 0; j < m; j++) {
		for(auto c: col[j]) {
			cols[c[0]][j].pb({c[1] - c[0] + 1, c[2]});
		}
		for(int i = 0; i < n; i++) {
			sort(all(cols[i][j]), [&](array<int, 2> x, array<int, 2> y) {
				return x[0] < y[0];
			});
		}
	}
	// cout << "zort" << endl;
	Fenwick st;
	st.reset(max(n, m) + 2);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int id = 0;
			for(auto c: rows[i][j]) {
				while(id < cols[i][j].size() && cols[i][j][id][0] <= c[1]) {
					st.update(cols[i][j][id][1], 1);
					id++;
				}
				ans += st.query(c[0], max(n, m));
			}
			while(id > 0) {
				id--;
				st.update(cols[i][j][id][1], -1);
			}
		}
	}
	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:110:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int k = 0; k  < ord.size(); k++) {
      |                  ~~~^~~~~~~~~~~~
rect.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for(int j = lind; j < ord.size(); j++) {
      |                     ~~^~~~~~~~~~~~
rect.cpp:148:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for(int k = 0; k < ord.size(); k++) {
      |                  ~~^~~~~~~~~~~~
rect.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |   for(int i = lind; i < ord.size(); i++) {
      |                     ~~^~~~~~~~~~~~
rect.cpp:227:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |     while(id < cols[i][j].size() && cols[i][j][id][0] <= c[1]) {
      |           ~~~^~~~~~~~~~~~~~~~~~~

• 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