oj.uz

Submission #285232

# Submission time Handle Problem Language Result Execution time Memory
285232 2020-08-28T12:31:33 Z cookiedoth Rectangles (IOI19_rect) C++14
100 / 100
 3939 ms 527648 KB 
/*

Code for problem C by cookiedoth
Generated 28 Aug 2020 at 01.11 PM


СТРОИМ КОММУНИЗМ РАБОТЯГИ!
 
                                    ╦═╩═╦═╩═█
                          ████▄▄▄═╦═╩═╦═╩═╦═█
                  ████████████████▄▄╦═╩═╦═╩═█
█═╦═╩═╦▄████████████████▀▀▀▀█████████▄╦═╩═╦═█
█═╩═╦═████████████████████▄═╦▀█████████═╦═╩═█
█═╦═▄██████████▀╩═╦═╩▄██████▄═╦▀████████▄═╦═█
█═╩═█████████▀╩═╦═╩═█████████▄╩═╦████████═╩═█
█═╦█████████▄═╦═╩═╦═▀█████████╦═╩═████████╦═█
█═╩███████████▄▄██▄═╦═▀████████═╦═████████╩═█
█═██████████████████▄═╦═▀█████▀═╩═█████████═█
█═████████████████████▄═╦═▀███╩═╦═█████████═█
█═╦████████████▀╩▀██████▄═╦═▀═╦═╩█████████╦═█
█═╩█████████▀═╩═╦═╩▀▀███▀▀╩═╦═╩═██████████╩═█
█═╦═██████▀═╦═▄▄█▄▄═╩═╦═╩═╦═╩═╦═╩▀███████═╦═█
█═╩═▀████═╩═▄█████████▄▄▄▄████▄═╦═╩█████▀═╩═█
█═╦═╩═██████████████████████████▄═▄████═╩═╦═█
█═╩═╦═╩▀█████████████████████████████▀╩═╦═╩═█
█═╦═╩═╦═╩▀▀███████████████████████▀▀╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═▀▀▀███████████████▀▀▀═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═▀▀▀▀▀▀▀▀▀═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█

o_O
^_^
~_^

*/

#include "rect.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

struct segment {
	int l, r, type, dp;
	segment(int _l, int _r): l(_l), r(_r), dp(0), type(0) {}
};

ostream& operator << (ostream &os, const segment &s) {
	os << s.l << ' ' << s.r << ' ' << s.type << ' ' << s.dp << '\n';
	return os;
}

bool operator < (const segment &a, const segment &b) {
	return make_pair(a.l, make_pair(a.r, a.type)) < make_pair(b.l, make_pair(b.r, b.type));
}

void find_segments(const vector<int> &arr, vector<segment> &vs) {
	// cerr << "find_segments" << endl;
	// output(all(arr));
	vector<int> rb;
	int len = arr.size();
	vector<int> st;
	for (int i = len - 1; i >= 0; --i) {
		rb.clear();
		int eq = 0;
		while (!st.empty() && arr[i] >= arr[st.back()]) {
			if (arr[i] == arr[st.back()]) {
				eq = 1;
			}
			rb.push_back(st.back());
			st.pop_back();
		}
		if (!st.empty() && !eq) {
			rb.push_back(st.back());
		}
		st.push_back(i);
		reverse(all(rb));
		for (auto r : rb) {
			if (r - 1 >= i + 1) {
				vs.emplace_back(i + 1, r - 1);
			}
		}
	}
	reverse(all(vs));
}

void calc_dp(vector<vector<segment> > &vvs) {
	for (int i = (int)vvs.size() - 2; i >= 1; --i) {
		for (auto &seg : vvs[i]) {
			auto it = lower_bound(all(vvs[i + 1]), seg);
			if (it != vvs[i + 1].end() && seg.l == it->l && seg.r == it->r) {
				seg.dp = it->dp + 1;
			} else {
				seg.dp = 1;
			}
		}
	}
}

int n, m;
vector<vector<int> > a, _a;
vector<vector<segment> > row_s, col_s;
ll ans;

void transpose_a() {
	_a.resize(m, vector<int> (n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			_a[j][i] = a[i][j];
		}
	}
}

void find_segments() {
	row_s.resize(n);
	for (int i = 1; i < n - 1; ++i) {
		find_segments(a[i], row_s[i]);
	}
	transpose_a();
	col_s.resize(m);
	for (int i = 1; i < m - 1; ++i) {
		find_segments(_a[i], col_s[i]);
	}
}

void calc_dp() {
	calc_dp(row_s);
	calc_dp(col_s);
}

void add_fake_segments() {
	for (int i = 1; i <= n - 2; ++i) {
		for (auto seg : row_s[i]) {
			segment cur(i, i + seg.dp - 1);
			cur.type = 1;
			cur.dp = -(seg.r - seg.l + 1);
			col_s[seg.l].push_back(cur);
		}
	}
	for (int i = 1; i <= m - 2; ++i) {
		sort(all(col_s[i]));
	}
}

struct fenwick {
	vector<int> t, used;
	int n, used_clr;

	void refresh(int pos) {
		if (used[pos] != used_clr) {
			used[pos] = used_clr;
			t[pos] = 0;
		}
	}

	void clear() {
		used_clr++;
	}
	
	void init(int _n) {
		n = _n;
		t.resize(n);
		used.resize(n);
	}

	void add(int pos, int val) {
		while (pos < n) {
			refresh(pos);
			t[pos] += val;
			pos = (pos | (pos + 1));
		}
	}

	int get(int r) {
		int res = 0;
		while (r >= 0) {
			refresh(r);
			res += t[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}

	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

void scanline() {
	fenwick f;
	f.init(m + 1);
	for (int i = 1; i <= m - 2; ++i) {
		f.clear();
		for (int j = 0; j < (int)col_s[i].size(); ++j) {
			if (col_s[i][j].type == 1) {
				ans += f.get(-col_s[i][j].dp, m);
			} else {
				f.add(col_s[i][j].dp, 1);
			}
			if (j < (int)col_s[i].size() - 1 && col_s[i][j].l != col_s[i][j + 1].l) {
				f.clear();
			}
		}
	}
}

ll count_rectangles(vector<vector<int> > _a0) {
	a = _a0;
	n = a.size();
	m = a[0].size();
	find_segments();
	calc_dp();
	add_fake_segments();
	scanline();
	return ans;
}

Compilation message

rect.cpp: In constructor 'segment::segment(int, int)':
rect.cpp:108:18: warning: 'segment::dp' will be initialized after [-Wreorder]
  108 |  int l, r, type, dp;
      |                  ^~
rect.cpp:108:12: warning:   'int segment::type' [-Wreorder]
  108 |  int l, r, type, dp;
      |            ^~~~
rect.cpp:109:2: warning:   when initialized here [-Wreorder]
  109 |  segment(int _l, int _r): l(_l), r(_r), dp(0), type(0) {}
      |  ^~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 2 ms 640 KB Output is correct
21 Correct 3 ms 896 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 0 ms 256 KB Output is correct
26 Correct 0 ms 256 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 0 ms 256 KB Output is correct
29 Correct 0 ms 256 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 2 ms 640 KB Output is correct
21 Correct 3 ms 896 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 15 ms 3416 KB Output is correct
26 Correct 15 ms 3328 KB Output is correct
27 Correct 16 ms 3328 KB Output is correct
28 Correct 9 ms 2304 KB Output is correct
29 Correct 18 ms 3584 KB Output is correct
30 Correct 19 ms 3456 KB Output is correct
31 Correct 20 ms 3456 KB Output is correct
32 Correct 18 ms 3328 KB Output is correct
33 Correct 0 ms 256 KB Output is correct
34 Correct 0 ms 256 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 0 ms 256 KB Output is correct
37 Correct 0 ms 256 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 2 ms 640 KB Output is correct
21 Correct 3 ms 896 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 15 ms 3416 KB Output is correct
26 Correct 15 ms 3328 KB Output is correct
27 Correct 16 ms 3328 KB Output is correct
28 Correct 9 ms 2304 KB Output is correct
29 Correct 18 ms 3584 KB Output is correct
30 Correct 19 ms 3456 KB Output is correct
31 Correct 20 ms 3456 KB Output is correct
32 Correct 18 ms 3328 KB Output is correct
33 Correct 109 ms 24056 KB Output is correct
34 Correct 97 ms 27000 KB Output is correct
35 Correct 108 ms 27128 KB Output is correct
36 Correct 93 ms 27000 KB Output is correct
37 Correct 238 ms 41848 KB Output is correct
38 Correct 241 ms 41848 KB Output is correct
39 Correct 248 ms 42224 KB Output is correct
40 Correct 224 ms 40440 KB Output is correct
41 Correct 74 ms 18040 KB Output is correct
42 Correct 113 ms 25080 KB Output is correct
43 Correct 283 ms 41600 KB Output is correct
44 Correct 273 ms 43512 KB Output is correct
45 Correct 132 ms 22136 KB Output is correct
46 Correct 137 ms 23048 KB Output is correct
47 Correct 265 ms 41064 KB Output is correct
48 Correct 247 ms 41756 KB Output is correct
49 Correct 0 ms 256 KB Output is correct
50 Correct 0 ms 256 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 0 ms 256 KB Output is correct
53 Correct 0 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 640 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 479 ms 98808 KB Output is correct
3 Correct 1079 ms 216440 KB Output is correct
4 Correct 1096 ms 219384 KB Output is correct
5 Correct 1103 ms 217240 KB Output is correct
6 Correct 147 ms 55032 KB Output is correct
7 Correct 265 ms 104184 KB Output is correct
8 Correct 283 ms 110840 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 2 ms 640 KB Output is correct
21 Correct 3 ms 896 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 15 ms 3416 KB Output is correct
26 Correct 15 ms 3328 KB Output is correct
27 Correct 16 ms 3328 KB Output is correct
28 Correct 9 ms 2304 KB Output is correct
29 Correct 18 ms 3584 KB Output is correct
30 Correct 19 ms 3456 KB Output is correct
31 Correct 20 ms 3456 KB Output is correct
32 Correct 18 ms 3328 KB Output is correct
33 Correct 109 ms 24056 KB Output is correct
34 Correct 97 ms 27000 KB Output is correct
35 Correct 108 ms 27128 KB Output is correct
36 Correct 93 ms 27000 KB Output is correct
37 Correct 238 ms 41848 KB Output is correct
38 Correct 241 ms 41848 KB Output is correct
39 Correct 248 ms 42224 KB Output is correct
40 Correct 224 ms 40440 KB Output is correct
41 Correct 74 ms 18040 KB Output is correct
42 Correct 113 ms 25080 KB Output is correct
43 Correct 283 ms 41600 KB Output is correct
44 Correct 273 ms 43512 KB Output is correct
45 Correct 132 ms 22136 KB Output is correct
46 Correct 137 ms 23048 KB Output is correct
47 Correct 265 ms 41064 KB Output is correct
48 Correct 247 ms 41756 KB Output is correct
49 Correct 2 ms 768 KB Output is correct
50 Correct 2 ms 768 KB Output is correct
51 Correct 1 ms 640 KB Output is correct
52 Correct 1 ms 256 KB Output is correct
53 Correct 2 ms 768 KB Output is correct
54 Correct 2 ms 768 KB Output is correct
55 Correct 2 ms 768 KB Output is correct
56 Correct 2 ms 768 KB Output is correct
57 Correct 2 ms 768 KB Output is correct
58 Correct 1 ms 512 KB Output is correct
59 Correct 1 ms 640 KB Output is correct
60 Correct 0 ms 256 KB Output is correct
61 Correct 479 ms 98808 KB Output is correct
62 Correct 1079 ms 216440 KB Output is correct
63 Correct 1096 ms 219384 KB Output is correct
64 Correct 1103 ms 217240 KB Output is correct
65 Correct 147 ms 55032 KB Output is correct
66 Correct 265 ms 104184 KB Output is correct
67 Correct 283 ms 110840 KB Output is correct
68 Correct 1621 ms 286456 KB Output is correct
69 Correct 1427 ms 282492 KB Output is correct
70 Correct 1599 ms 277236 KB Output is correct
71 Correct 1308 ms 280300 KB Output is correct
72 Correct 3887 ms 493452 KB Output is correct
73 Correct 2207 ms 287580 KB Output is correct
74 Correct 2439 ms 328128 KB Output is correct
75 Correct 3772 ms 500636 KB Output is correct
76 Correct 2518 ms 304120 KB Output is correct
77 Correct 3081 ms 416132 KB Output is correct
78 Correct 3939 ms 527648 KB Output is correct
79 Correct 2015 ms 289104 KB Output is correct
80 Correct 3489 ms 513476 KB Output is correct
81 Correct 3481 ms 498460 KB Output is correct
82 Correct 2341 ms 313180 KB Output is correct
83 Correct 3793 ms 514660 KB Output is correct
84 Correct 3718 ms 515120 KB Output is correct
85 Correct 3747 ms 515340 KB Output is correct
86 Correct 0 ms 256 KB Output is correct
87 Correct 0 ms 256 KB Output is correct
88 Correct 1 ms 384 KB Output is correct
89 Correct 0 ms 256 KB Output is correct
90 Correct 0 ms 256 KB Output is correct