oj.uz

Submission #569670

# Submission time Handle Problem Language Result Execution time Memory
569670 2022-05-27T15:31:59 Z ngpin04 Rectangles (IOI19_rect) C++17
100 / 100
 4200 ms 1037044 KB 
#include "rect.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 2505;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <pair <int, int>> sr[N][N], sc[N][N];
vector <tuple <int, int, int>> events[N];
vector <int> col[N][N];
vector <int> row[N];

int pos[N][N];
int limc[N][N];
int lim[N][N];
int a[N][N];
int bit[N];
int v[N];
int l[N];
int r[N];
int n,m;

void update(int pos, int val) {
	for (; pos <= m; pos += pos & -pos)
		bit[pos] += val;
}

int getsum(int pos) {
	int res = 0;
	for (; pos; pos -= pos & -pos)
		res += bit[pos];
	return res;
}

void findmax(int a[], int l[], int n) {
	vector <int> s;
	s.push_back(0);
	a[0] = oo;
	for (int i = 1; i <= n; i++) {
		while (a[i] > a[s.back()]) 
			s.pop_back();
		l[i] = s.back();
		s.push_back(i);
	}
}

void addrow(int i, int u, int v) {
	if (sr[u][v].size() && sr[u][v].back().se == i - 1)
		sr[u][v].back().se = i;
	else
		sr[u][v].push_back(mp(i, i));
}

void addcol(int j, int u, int v) {
	if (sc[u][v].size() && sc[u][v].back().se == j - 1) 
		sc[u][v].back().se = j;
	else
		sc[u][v].push_back(mp(j, j));
	col[u][j].push_back(v);
}

void build() {
	for (int i = 1; i <= n; i++) {
		findmax(a[i], l, m);
		reverse(a[i] + 1, a[i] + m + 1);
		findmax(a[i], r, m);
		reverse(a[i] + 1, a[i] + m + 1);
		reverse(r + 1, r + m + 1);
		for (int j = 1; j <= m; j++)
			r[j] = (m - r[j] + 1);
	
		for (int j = 1; j <= m; j++) {
			if (l[j] > 0 && l[j] != j - 1) {
				auto [u, v] = mp(l[j], j);
				addrow(i, u, v);
			}

			if (r[j] <= m && r[j] != j + 1 && a[i][j] < a[i][r[j]]) {
				auto [u, v] = mp(j, r[j]);
				addrow(i, u, v);
			}
		}	
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++)
			v[i] = a[i][j];

		findmax(v, l, n);
		reverse(v + 1, v + n + 1);
		findmax(v, r, n);
		reverse(r + 1, r + n + 1);

		for (int i = 1; i <= n; i++)
			r[i] = (n - r[i] + 1);
	
		for (int i = 1; i <= n; i++) {
			if (l[i] > 0 && l[i] != i - 1) {
				auto [u, v] = mp(l[i], i);
				addcol(j, u, v);
			}

			if (r[i] <= n && r[i] != i + 1 && a[i][j] < a[r[i]][j]) {
				auto [u, v] = mp(i, r[i]);
				addcol(j, u, v);
			}
		}
	}

	for (int l = 1; l <= m; l++)
	for (int r = l + 1; r <= m; r++) 
	for (auto [u, v] : sr[l][r]) {
		// for (int j = u; j <= v; j++)
		// 	events[j].push_back({l, r});
		
		events[u].push_back({l, r, v});
		events[v + 1].push_back({-l, -r, -v});
	}
}

int solve() {
	build();
	int res = 0;

	vector <pair <int, int>> cand;

	for (int i = 1; i < n; i++) {
		for (auto [l, r, v] : events[i]) {
			if (l > 0) {
				pos[l][r] = cand.size();
				lim[l][r] = v;
				cand.push_back({l, r});
			} else {
				l = -l, r = -r;
				pos[cand.back().fi][cand.back().se] = pos[l][r];
				swap(cand[pos[l][r]], cand.back());
				cand.pop_back();
			}
		}

		if (i == 1)
			continue;

		for (int j = 1; j <= m; j++) 
			row[j].clear();

		for (auto [l, r] : cand)
			row[l].push_back(r);

		for (int l = 1; l <= m; l++) {
			sort(ALL(row[l]), [&](int i, int j) {
				return lim[l][i] < lim[l][j];
			});

			sort(ALL(col[i - 1][l + 1]));

			vector <int> p;
			const vector <int> &f = row[l];
			const vector <int> &g = col[i - 1][l + 1];
			for (int it = 0, jt = 0; it < (int) f.size(); it++) {
				int r = f[it];
				// cerr << "seg " << i << " " << l << " " << r << " " << lim[l][r] << "\n";
				while (jt < (int) g.size()) {
					int k = g[jt];

					if (k <= lim[l][r] + 1) {
						// cerr << "update " << i - 1 << " " << k  << "\n";
						pair <int, int> to_find = {l + 1, oo};
						int tmp = prev(upper_bound(ALL(sc[i - 1][k]), to_find))->se;
						update(tmp, 1);
						p.push_back(tmp);
						jt++;
						continue;
					}
					break;
				}

				res += getsum(m) - getsum(r - 2);
				// cerr << res << "\n";
			}

			for (int lim : p)
				update(lim, -1);
		}
	}

	return res;
}

long long count_rectangles(vector<vector<int>> _a) {
	n = _a.size();
	m = _a[0].size();
	for (int i = 1; i <= n; i++) 
	for (int j = 1; j <= m; j++)
		a[i][j] = _a[i - 1][j - 1];
	return solve();
}

//#include "grader.cpp"

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 442544 KB Output is correct
2 Correct 207 ms 442908 KB Output is correct
3 Correct 204 ms 442876 KB Output is correct
4 Correct 203 ms 442820 KB Output is correct
5 Correct 214 ms 442640 KB Output is correct
6 Correct 216 ms 442892 KB Output is correct
7 Correct 206 ms 442724 KB Output is correct
8 Correct 216 ms 442836 KB Output is correct
9 Correct 223 ms 442888 KB Output is correct
10 Correct 210 ms 442828 KB Output is correct
11 Correct 207 ms 442936 KB Output is correct
12 Correct 208 ms 442900 KB Output is correct
13 Correct 204 ms 442376 KB Output is correct
14 Correct 208 ms 442444 KB Output is correct
15 Correct 205 ms 442420 KB Output is correct
16 Correct 204 ms 442500 KB Output is correct
17 Correct 204 ms 442424 KB Output is correct
18 Correct 285 ms 442620 KB Output is correct
19 Correct 203 ms 442956 KB Output is correct
20 Correct 205 ms 442584 KB Output is correct
21 Correct 203 ms 442484 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 442544 KB Output is correct
2 Correct 207 ms 442908 KB Output is correct
3 Correct 204 ms 442876 KB Output is correct
4 Correct 203 ms 442820 KB Output is correct
5 Correct 214 ms 442640 KB Output is correct
6 Correct 216 ms 442892 KB Output is correct
7 Correct 206 ms 442724 KB Output is correct
8 Correct 216 ms 442836 KB Output is correct
9 Correct 223 ms 442888 KB Output is correct
10 Correct 210 ms 442828 KB Output is correct
11 Correct 207 ms 442936 KB Output is correct
12 Correct 208 ms 442900 KB Output is correct
13 Correct 204 ms 442376 KB Output is correct
14 Correct 208 ms 442444 KB Output is correct
15 Correct 205 ms 442420 KB Output is correct
16 Correct 204 ms 442500 KB Output is correct
17 Correct 204 ms 442424 KB Output is correct
18 Correct 285 ms 442620 KB Output is correct
19 Correct 203 ms 442956 KB Output is correct
20 Correct 205 ms 442584 KB Output is correct
21 Correct 203 ms 442484 KB Output is correct
22 Correct 205 ms 443704 KB Output is correct
23 Correct 211 ms 443800 KB Output is correct
24 Correct 202 ms 443712 KB Output is correct
25 Correct 235 ms 443684 KB Output is correct
26 Correct 206 ms 443936 KB Output is correct
27 Correct 211 ms 443984 KB Output is correct
28 Correct 205 ms 443896 KB Output is correct
29 Correct 207 ms 443272 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 442544 KB Output is correct
2 Correct 207 ms 442908 KB Output is correct
3 Correct 204 ms 442876 KB Output is correct
4 Correct 203 ms 442820 KB Output is correct
5 Correct 214 ms 442640 KB Output is correct
6 Correct 216 ms 442892 KB Output is correct
7 Correct 206 ms 442724 KB Output is correct
8 Correct 216 ms 442836 KB Output is correct
9 Correct 223 ms 442888 KB Output is correct
10 Correct 210 ms 442828 KB Output is correct
11 Correct 207 ms 442936 KB Output is correct
12 Correct 208 ms 442900 KB Output is correct
13 Correct 204 ms 442376 KB Output is correct
14 Correct 208 ms 442444 KB Output is correct
15 Correct 205 ms 442420 KB Output is correct
16 Correct 204 ms 442500 KB Output is correct
17 Correct 205 ms 443704 KB Output is correct
18 Correct 211 ms 443800 KB Output is correct
19 Correct 202 ms 443712 KB Output is correct
20 Correct 235 ms 443684 KB Output is correct
21 Correct 206 ms 443936 KB Output is correct
22 Correct 211 ms 443984 KB Output is correct
23 Correct 205 ms 443896 KB Output is correct
24 Correct 207 ms 443272 KB Output is correct
25 Correct 204 ms 442424 KB Output is correct
26 Correct 285 ms 442620 KB Output is correct
27 Correct 203 ms 442956 KB Output is correct
28 Correct 205 ms 442584 KB Output is correct
29 Correct 203 ms 442484 KB Output is correct
30 Correct 214 ms 446904 KB Output is correct
31 Correct 212 ms 446848 KB Output is correct
32 Correct 212 ms 446904 KB Output is correct
33 Correct 213 ms 446924 KB Output is correct
34 Correct 226 ms 448468 KB Output is correct
35 Correct 224 ms 448628 KB Output is correct
36 Correct 226 ms 447836 KB Output is correct
37 Correct 218 ms 447972 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 442544 KB Output is correct
2 Correct 207 ms 442908 KB Output is correct
3 Correct 204 ms 442876 KB Output is correct
4 Correct 203 ms 442820 KB Output is correct
5 Correct 214 ms 442640 KB Output is correct
6 Correct 216 ms 442892 KB Output is correct
7 Correct 206 ms 442724 KB Output is correct
8 Correct 216 ms 442836 KB Output is correct
9 Correct 223 ms 442888 KB Output is correct
10 Correct 210 ms 442828 KB Output is correct
11 Correct 207 ms 442936 KB Output is correct
12 Correct 208 ms 442900 KB Output is correct
13 Correct 204 ms 442376 KB Output is correct
14 Correct 208 ms 442444 KB Output is correct
15 Correct 205 ms 442420 KB Output is correct
16 Correct 204 ms 442500 KB Output is correct
17 Correct 205 ms 443704 KB Output is correct
18 Correct 211 ms 443800 KB Output is correct
19 Correct 202 ms 443712 KB Output is correct
20 Correct 235 ms 443684 KB Output is correct
21 Correct 206 ms 443936 KB Output is correct
22 Correct 211 ms 443984 KB Output is correct
23 Correct 205 ms 443896 KB Output is correct
24 Correct 207 ms 443272 KB Output is correct
25 Correct 214 ms 446904 KB Output is correct
26 Correct 212 ms 446848 KB Output is correct
27 Correct 212 ms 446904 KB Output is correct
28 Correct 213 ms 446924 KB Output is correct
29 Correct 226 ms 448468 KB Output is correct
30 Correct 224 ms 448628 KB Output is correct
31 Correct 226 ms 447836 KB Output is correct
32 Correct 218 ms 447972 KB Output is correct
33 Correct 204 ms 442424 KB Output is correct
34 Correct 285 ms 442620 KB Output is correct
35 Correct 203 ms 442956 KB Output is correct
36 Correct 205 ms 442584 KB Output is correct
37 Correct 203 ms 442484 KB Output is correct
38 Correct 331 ms 491232 KB Output is correct
39 Correct 335 ms 492016 KB Output is correct
40 Correct 289 ms 485068 KB Output is correct
41 Correct 284 ms 486188 KB Output is correct
42 Correct 340 ms 473568 KB Output is correct
43 Correct 345 ms 473628 KB Output is correct
44 Correct 348 ms 473712 KB Output is correct
45 Correct 347 ms 472228 KB Output is correct
46 Correct 297 ms 468932 KB Output is correct
47 Correct 336 ms 471136 KB Output is correct
48 Correct 451 ms 492968 KB Output is correct
49 Correct 459 ms 494284 KB Output is correct
50 Correct 336 ms 470008 KB Output is correct
51 Correct 350 ms 471476 KB Output is correct
52 Correct 428 ms 482656 KB Output is correct
53 Correct 447 ms 483788 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 463052 KB Output is correct
2 Correct 240 ms 460048 KB Output is correct
3 Correct 255 ms 442532 KB Output is correct
4 Correct 222 ms 442396 KB Output is correct
5 Correct 238 ms 458800 KB Output is correct
6 Correct 245 ms 458140 KB Output is correct
7 Correct 268 ms 458420 KB Output is correct
8 Correct 249 ms 457296 KB Output is correct
9 Correct 252 ms 457128 KB Output is correct
10 Correct 247 ms 442844 KB Output is correct
11 Correct 266 ms 453204 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 442424 KB Output is correct
2 Correct 285 ms 442620 KB Output is correct
3 Correct 203 ms 442956 KB Output is correct
4 Correct 205 ms 442584 KB Output is correct
5 Correct 203 ms 442484 KB Output is correct
6 Correct 214 ms 442572 KB Output is correct
7 Correct 892 ms 562864 KB Output is correct
8 Correct 1672 ms 682888 KB Output is correct
9 Correct 1701 ms 683712 KB Output is correct
10 Correct 1714 ms 683580 KB Output is correct
11 Correct 360 ms 481024 KB Output is correct
12 Correct 501 ms 515468 KB Output is correct
13 Correct 517 ms 518416 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 442544 KB Output is correct
2 Correct 207 ms 442908 KB Output is correct
3 Correct 204 ms 442876 KB Output is correct
4 Correct 203 ms 442820 KB Output is correct
5 Correct 214 ms 442640 KB Output is correct
6 Correct 216 ms 442892 KB Output is correct
7 Correct 206 ms 442724 KB Output is correct
8 Correct 216 ms 442836 KB Output is correct
9 Correct 223 ms 442888 KB Output is correct
10 Correct 210 ms 442828 KB Output is correct
11 Correct 207 ms 442936 KB Output is correct
12 Correct 208 ms 442900 KB Output is correct
13 Correct 204 ms 442376 KB Output is correct
14 Correct 208 ms 442444 KB Output is correct
15 Correct 205 ms 442420 KB Output is correct
16 Correct 204 ms 442500 KB Output is correct
17 Correct 205 ms 443704 KB Output is correct
18 Correct 211 ms 443800 KB Output is correct
19 Correct 202 ms 443712 KB Output is correct
20 Correct 235 ms 443684 KB Output is correct
21 Correct 206 ms 443936 KB Output is correct
22 Correct 211 ms 443984 KB Output is correct
23 Correct 205 ms 443896 KB Output is correct
24 Correct 207 ms 443272 KB Output is correct
25 Correct 214 ms 446904 KB Output is correct
26 Correct 212 ms 446848 KB Output is correct
27 Correct 212 ms 446904 KB Output is correct
28 Correct 213 ms 446924 KB Output is correct
29 Correct 226 ms 448468 KB Output is correct
30 Correct 224 ms 448628 KB Output is correct
31 Correct 226 ms 447836 KB Output is correct
32 Correct 218 ms 447972 KB Output is correct
33 Correct 331 ms 491232 KB Output is correct
34 Correct 335 ms 492016 KB Output is correct
35 Correct 289 ms 485068 KB Output is correct
36 Correct 284 ms 486188 KB Output is correct
37 Correct 340 ms 473568 KB Output is correct
38 Correct 345 ms 473628 KB Output is correct
39 Correct 348 ms 473712 KB Output is correct
40 Correct 347 ms 472228 KB Output is correct
41 Correct 297 ms 468932 KB Output is correct
42 Correct 336 ms 471136 KB Output is correct
43 Correct 451 ms 492968 KB Output is correct
44 Correct 459 ms 494284 KB Output is correct
45 Correct 336 ms 470008 KB Output is correct
46 Correct 350 ms 471476 KB Output is correct
47 Correct 428 ms 482656 KB Output is correct
48 Correct 447 ms 483788 KB Output is correct
49 Correct 243 ms 463052 KB Output is correct
50 Correct 240 ms 460048 KB Output is correct
51 Correct 255 ms 442532 KB Output is correct
52 Correct 222 ms 442396 KB Output is correct
53 Correct 238 ms 458800 KB Output is correct
54 Correct 245 ms 458140 KB Output is correct
55 Correct 268 ms 458420 KB Output is correct
56 Correct 249 ms 457296 KB Output is correct
57 Correct 252 ms 457128 KB Output is correct
58 Correct 247 ms 442844 KB Output is correct
59 Correct 266 ms 453204 KB Output is correct
60 Correct 214 ms 442572 KB Output is correct
61 Correct 892 ms 562864 KB Output is correct
62 Correct 1672 ms 682888 KB Output is correct
63 Correct 1701 ms 683712 KB Output is correct
64 Correct 1714 ms 683580 KB Output is correct
65 Correct 360 ms 481024 KB Output is correct
66 Correct 501 ms 515468 KB Output is correct
67 Correct 517 ms 518416 KB Output is correct
68 Correct 204 ms 442424 KB Output is correct
69 Correct 285 ms 442620 KB Output is correct
70 Correct 203 ms 442956 KB Output is correct
71 Correct 205 ms 442584 KB Output is correct
72 Correct 203 ms 442484 KB Output is correct
73 Correct 2733 ms 950644 KB Output is correct
74 Correct 2265 ms 948872 KB Output is correct
75 Correct 1604 ms 865468 KB Output is correct
76 Correct 1198 ms 867940 KB Output is correct
77 Correct 2824 ms 732808 KB Output is correct
78 Correct 2321 ms 770088 KB Output is correct
79 Correct 2455 ms 777868 KB Output is correct
80 Correct 3885 ms 960820 KB Output is correct
81 Correct 2458 ms 810880 KB Output is correct
82 Correct 3304 ms 881084 KB Output is correct
83 Correct 4200 ms 1037044 KB Output is correct
84 Correct 2138 ms 715892 KB Output is correct
85 Correct 3719 ms 901048 KB Output is correct
86 Correct 3592 ms 883520 KB Output is correct
87 Correct 1657 ms 654904 KB Output is correct
88 Correct 3054 ms 779756 KB Output is correct
89 Correct 2969 ms 780028 KB Output is correct
90 Correct 2952 ms 779908 KB Output is correct