oj.uz

Submission #1049382

# Submission time Handle Problem Language Result Execution time Memory
1049382 2024-08-08T17:45:26 Z efedmrlr Rectangles (IOI19_rect) C++17
100 / 100
 3460 ms 781904 KB 
#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<vector<array<int, 2> > > > rows(n, vector<vector<array<int, 2> > >(m)), cols(n, vector<vector<array<int, 2> > >(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;
					rows[i][ds.l[ds.find_set(ord[j])]].pb({ds.r[ds.find_set(ord[j])] - ds.l[ds.find_set(ord[j])] + 1, 0});
				}
				
				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;
				rows[i][ds.l[ds.find_set(ord[j])]].pb({ds.r[ds.find_set(ord[j])] - ds.l[ds.find_set(ord[j])] + 1, 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;
					cols[ds.l[ds.find_set(ord[i])]][j].pb({ds.r[ds.find_set(ord[i])] - ds.l[ds.find_set(ord[i])] + 1, 0});
				}
				
				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;
				cols[ds.l[ds.find_set(ord[i])]][j].pb({ds.r[ds.find_set(ord[i])] - ds.l[ds.find_set(ord[i])] + 1, 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";
	// 	}
	// } 
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			sort(all(rows[i][j]));
			sort(all(cols[i][j]));
		}
	}
	for(int i = n - 1; i >= 0; i--) {
		for(int j = m - 1; j >= 0; j--) {
			// cout << "i:" << i << " j:" << j << "\n";
			// cout << "rows: \n";
			for(auto &c : rows[i][j]) {
				c[1] = 1;
				if(i == n - 1) continue;
				auto x = lower_bound(all(rows[i + 1][j]), c);
				if(x == rows[i + 1][j].end() || (*x)[0] != c[0]) {
					continue;
				}
				c[1] = (*x)[1] + 1;
				// cout << c[0] << " " << c[1] << "\n";
			}
			// cout << "cols: \n";
			for(auto &c : cols[i][j]) {
				c[1] = 1;
				if(j == m - 1) continue;
				auto x = lower_bound(all(cols[i][j + 1]), c);
				if(x == cols[i][j + 1].end() || (*x)[0] != c[0]) {
					continue;
				}
				c[1] = (*x)[1] + 1;
				// cout << c[0] << " " << c[1] << "\n";
			}
		}
	}
	// cout << "zort" << endl;
	for(int i = 0; i < n; i++) {
		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];
			});
		}
	}
	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

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:231: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]
  231 |     while(id < cols[i][j].size() && cols[i][j][id][0] <= c[1]) {
      |           ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 2 ms 1116 KB Output is correct
23 Correct 2 ms 1116 KB Output is correct
24 Correct 3 ms 1112 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 3 ms 828 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 1 ms 604 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 1116 KB Output is correct
18 Correct 2 ms 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 3 ms 828 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 10 ms 5212 KB Output is correct
31 Correct 10 ms 5212 KB Output is correct
32 Correct 10 ms 5180 KB Output is correct
33 Correct 8 ms 3548 KB Output is correct
34 Correct 12 ms 4188 KB Output is correct
35 Correct 12 ms 4220 KB Output is correct
36 Correct 12 ms 4188 KB Output is correct
37 Correct 12 ms 4220 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 1116 KB Output is correct
18 Correct 2 ms 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 3 ms 828 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 10 ms 5212 KB Output is correct
26 Correct 10 ms 5212 KB Output is correct
27 Correct 10 ms 5180 KB Output is correct
28 Correct 8 ms 3548 KB Output is correct
29 Correct 12 ms 4188 KB Output is correct
30 Correct 12 ms 4220 KB Output is correct
31 Correct 12 ms 4188 KB Output is correct
32 Correct 12 ms 4220 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 96 ms 44368 KB Output is correct
39 Correct 83 ms 39552 KB Output is correct
40 Correct 76 ms 39532 KB Output is correct
41 Correct 66 ms 34688 KB Output is correct
42 Correct 147 ms 59476 KB Output is correct
43 Correct 147 ms 59472 KB Output is correct
44 Correct 153 ms 59988 KB Output is correct
45 Correct 139 ms 56144 KB Output is correct
46 Correct 95 ms 35668 KB Output is correct
47 Correct 111 ms 38084 KB Output is correct
48 Correct 207 ms 46552 KB Output is correct
49 Correct 206 ms 47440 KB Output is correct
50 Correct 92 ms 24144 KB Output is correct
51 Correct 93 ms 24416 KB Output is correct
52 Correct 194 ms 45292 KB Output is correct
53 Correct 197 ms 45908 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 432 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 1 ms 784 KB Output is correct
8 Correct 1 ms 988 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 567 ms 205364 KB Output is correct
8 Correct 1336 ms 444928 KB Output is correct
9 Correct 1323 ms 447144 KB Output is correct
10 Correct 1294 ms 447380 KB Output is correct
11 Correct 220 ms 172812 KB Output is correct
12 Correct 460 ms 327720 KB Output is correct
13 Correct 483 ms 349572 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 1116 KB Output is correct
18 Correct 2 ms 1116 KB Output is correct
19 Correct 3 ms 1112 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 3 ms 828 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 10 ms 5212 KB Output is correct
26 Correct 10 ms 5212 KB Output is correct
27 Correct 10 ms 5180 KB Output is correct
28 Correct 8 ms 3548 KB Output is correct
29 Correct 12 ms 4188 KB Output is correct
30 Correct 12 ms 4220 KB Output is correct
31 Correct 12 ms 4188 KB Output is correct
32 Correct 12 ms 4220 KB Output is correct
33 Correct 96 ms 44368 KB Output is correct
34 Correct 83 ms 39552 KB Output is correct
35 Correct 76 ms 39532 KB Output is correct
36 Correct 66 ms 34688 KB Output is correct
37 Correct 147 ms 59476 KB Output is correct
38 Correct 147 ms 59472 KB Output is correct
39 Correct 153 ms 59988 KB Output is correct
40 Correct 139 ms 56144 KB Output is correct
41 Correct 95 ms 35668 KB Output is correct
42 Correct 111 ms 38084 KB Output is correct
43 Correct 207 ms 46552 KB Output is correct
44 Correct 206 ms 47440 KB Output is correct
45 Correct 92 ms 24144 KB Output is correct
46 Correct 93 ms 24416 KB Output is correct
47 Correct 194 ms 45292 KB Output is correct
48 Correct 197 ms 45908 KB Output is correct
49 Correct 2 ms 860 KB Output is correct
50 Correct 1 ms 860 KB Output is correct
51 Correct 1 ms 860 KB Output is correct
52 Correct 0 ms 432 KB Output is correct
53 Correct 2 ms 856 KB Output is correct
54 Correct 2 ms 856 KB Output is correct
55 Correct 1 ms 784 KB Output is correct
56 Correct 1 ms 988 KB Output is correct
57 Correct 1 ms 860 KB Output is correct
58 Correct 1 ms 604 KB Output is correct
59 Correct 1 ms 600 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 567 ms 205364 KB Output is correct
62 Correct 1336 ms 444928 KB Output is correct
63 Correct 1323 ms 447144 KB Output is correct
64 Correct 1294 ms 447380 KB Output is correct
65 Correct 220 ms 172812 KB Output is correct
66 Correct 460 ms 327720 KB Output is correct
67 Correct 483 ms 349572 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 0 ms 348 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 1501 ms 562448 KB Output is correct
74 Correct 1339 ms 495280 KB Output is correct
75 Correct 1096 ms 471588 KB Output is correct
76 Correct 906 ms 404816 KB Output is correct
77 Correct 2315 ms 734000 KB Output is correct
78 Correct 1880 ms 358064 KB Output is correct
79 Correct 2060 ms 385868 KB Output is correct
80 Correct 3417 ms 596760 KB Output is correct
81 Correct 1910 ms 374424 KB Output is correct
82 Correct 2701 ms 499144 KB Output is correct
83 Correct 3460 ms 623996 KB Output is correct
84 Correct 1811 ms 356452 KB Output is correct
85 Correct 3234 ms 607856 KB Output is correct
86 Correct 3145 ms 590168 KB Output is correct
87 Correct 1345 ms 469444 KB Output is correct
88 Correct 2405 ms 781252 KB Output is correct
89 Correct 2440 ms 781904 KB Output is correct
90 Correct 2570 ms 781888 KB Output is correct