oj.uz

Submission #956959

# Submission time Handle Problem Language Result Execution time Memory
956959 2024-04-02T18:02:45 Z Macker Rectangles (IOI19_rect) C++17
59 / 100
 5000 ms 954456 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

struct node{
	int on = 0, mxx, mnx, mxy, mny;
};
vector<vector<node>> st;
int lenx = 1, leny = 1;
node zero({1, 0, INT_MAX/2, 0, INT_MAX/2});

vector<int> get_last_big(vector<int> v){
	int n = v.size();
	vector<int> res(n, -1);
	stack<pii> s;
	s.push({INT_MAX/2, -1});
	FOR(i, n){
		int a = v[i];
		while(a >= s.top().ff) s.pop();
		res[i] = s.top().ss;
		s.push({a, i});
	}
	return res;
}

node comb(node a, node b){
	node res;
	res.on = min(a.on, b.on);
	res.mnx = min(a.mnx, b.mnx);
	res.mny = min(a.mny, b.mny);
	res.mxx = max(a.mxx, b.mxx);
	res.mxy = max(a.mxy, b.mxy);
	return res;
}

void updy(int y, node val, int i, int j = 1, int s = 0, int e = leny){
	if(y < s || y >= e) return;
	if(y == s && s + 1 == e) {
		if(i >= lenx) st[i][j] = val;
		else st[i][j] = comb(st[i * 2][j], st[i * 2 + 1][j]);
		return;
	}

	updy(y, val, i, j * 2, s, (s + e) / 2);
	updy(y, val, i, j * 2 + 1, (s + e) / 2, e);
	st[i][j] = comb(st[i][j * 2], st[i][j * 2 + 1]);
}

void updx(int x, int y, node val, int i = 1, int s = 0, int e = lenx){
	if(x < s || x >= e) return;
	if(x == s && s + 1 == e) {updy(y, val, i); return;}

	updx(x, y, val, i * 2, s, (s + e) / 2);
	updx(x, y, val, i * 2 + 1, (s + e) / 2, e);
	
	updy(y, val, i);
}

node qryy(int l, int r, int i, int j = 1, int s = 0, int e = leny){
	if(l >= e || r <= s) return zero;
	if(l <= s && e <= r) return st[i][j];

	return comb(qryy(l, r, i, j * 2, s, (s + e) / 2),
				qryy(l, r, i, j * 2 + 1, (s + e) / 2, e));
}

node qryx(int xl, int xr, int yl, int yr, int i = 1, int s = 0, int e = lenx){
	if(xl >= e || xr <= s) return zero;
	if(xl <= s && e <= xr) return qryy(yl, yr, i);

	return comb(qryx(xl, xr, yl, yr, i * 2, s, (s + e) / 2),
				qryx(xl, xr, yl, yr, i * 2 + 1, (s + e) / 2, e));
}

long long count_rectangles(vector<vector<signed>> v) {
	int n = v.size();
	while(lenx < n) lenx *= 2;
	int m = v[0].size();
	while(leny < m) leny *= 2;
	st.assign(2 * lenx, vector<node>(2 * leny));
	vector<vector<node>> passive(n, vector<node>(m));

	FOR(i, n){
		vector<int> cur;
		vector<int> res;
		FOR(j, m){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(j, m){
			passive[i][j].mnx = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, m){
			passive[i][j].mxx = m - res[j] - 1;
		}
	}
	FOR(j, m){
		vector<int> cur;
		vector<int> res;
		FOR(i, n){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(i, n){
			passive[i][j].mny = res[i];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(i, n){
			passive[i][j].mxy = n - res[i] - 1;
		}
	}
	
	vector<vector<pii>> ord(7000005);
	FOR(i, n) FOR(j, m){
		ord[v[i][j]].push_back({i, j});
	}
	ll res = 0;
	for (auto o : ord) {
		for (auto [x, y] : o) {
			passive[x][y].on = true;
			updx(x, y, passive[x][y]);

			int mnx = passive[x][y].mnx;
			int mny = passive[x][y].mny;
			int mxx = passive[x][y].mxx;
			int mxy = passive[x][y].mxy;

			if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue;
			
			node ret = qryx(
				mny + 1,
				mxy,
				mnx + 1,
				mxx
			);
			bool f = 0;
			if(!ret.on) f = 1;
			if(ret.mnx < mnx) f = 1;
			if(ret.mny < mny) f = 1;
			if(ret.mxx > mxx) f = 1;
			if(ret.mxy > mxy) f = 1;

			if(!f)
				res++;
		}
	}
	return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164692 KB Output is correct
2 Correct 69 ms 164944 KB Output is correct
3 Correct 59 ms 164784 KB Output is correct
4 Correct 77 ms 164692 KB Output is correct
5 Correct 68 ms 164816 KB Output is correct
6 Correct 57 ms 164952 KB Output is correct
7 Correct 82 ms 164644 KB Output is correct
8 Correct 54 ms 164696 KB Output is correct
9 Correct 55 ms 164688 KB Output is correct
10 Correct 89 ms 164692 KB Output is correct
11 Correct 54 ms 164692 KB Output is correct
12 Correct 87 ms 164948 KB Output is correct
13 Correct 69 ms 164668 KB Output is correct
14 Correct 54 ms 164692 KB Output is correct
15 Correct 88 ms 164652 KB Output is correct
16 Correct 102 ms 164796 KB Output is correct
17 Correct 58 ms 164684 KB Output is correct
18 Correct 80 ms 164696 KB Output is correct
19 Correct 83 ms 164716 KB Output is correct
20 Correct 69 ms 164812 KB Output is correct
21 Correct 55 ms 164744 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164692 KB Output is correct
2 Correct 69 ms 164944 KB Output is correct
3 Correct 59 ms 164784 KB Output is correct
4 Correct 77 ms 164692 KB Output is correct
5 Correct 68 ms 164816 KB Output is correct
6 Correct 57 ms 164952 KB Output is correct
7 Correct 82 ms 164644 KB Output is correct
8 Correct 54 ms 164696 KB Output is correct
9 Correct 55 ms 164688 KB Output is correct
10 Correct 89 ms 164692 KB Output is correct
11 Correct 54 ms 164692 KB Output is correct
12 Correct 87 ms 164948 KB Output is correct
13 Correct 69 ms 164668 KB Output is correct
14 Correct 54 ms 164692 KB Output is correct
15 Correct 88 ms 164652 KB Output is correct
16 Correct 102 ms 164796 KB Output is correct
17 Correct 58 ms 164684 KB Output is correct
18 Correct 80 ms 164696 KB Output is correct
19 Correct 83 ms 164716 KB Output is correct
20 Correct 69 ms 164812 KB Output is correct
21 Correct 55 ms 164744 KB Output is correct
22 Correct 97 ms 166372 KB Output is correct
23 Correct 93 ms 166644 KB Output is correct
24 Correct 67 ms 166484 KB Output is correct
25 Correct 95 ms 166228 KB Output is correct
26 Correct 70 ms 166232 KB Output is correct
27 Correct 63 ms 166484 KB Output is correct
28 Correct 61 ms 166168 KB Output is correct
29 Correct 58 ms 165556 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164692 KB Output is correct
2 Correct 69 ms 164944 KB Output is correct
3 Correct 59 ms 164784 KB Output is correct
4 Correct 77 ms 164692 KB Output is correct
5 Correct 68 ms 164816 KB Output is correct
6 Correct 57 ms 164952 KB Output is correct
7 Correct 82 ms 164644 KB Output is correct
8 Correct 54 ms 164696 KB Output is correct
9 Correct 55 ms 164688 KB Output is correct
10 Correct 89 ms 164692 KB Output is correct
11 Correct 54 ms 164692 KB Output is correct
12 Correct 87 ms 164948 KB Output is correct
13 Correct 69 ms 164668 KB Output is correct
14 Correct 54 ms 164692 KB Output is correct
15 Correct 88 ms 164652 KB Output is correct
16 Correct 102 ms 164796 KB Output is correct
17 Correct 97 ms 166372 KB Output is correct
18 Correct 93 ms 166644 KB Output is correct
19 Correct 67 ms 166484 KB Output is correct
20 Correct 95 ms 166228 KB Output is correct
21 Correct 70 ms 166232 KB Output is correct
22 Correct 63 ms 166484 KB Output is correct
23 Correct 61 ms 166168 KB Output is correct
24 Correct 58 ms 165556 KB Output is correct
25 Correct 58 ms 164684 KB Output is correct
26 Correct 80 ms 164696 KB Output is correct
27 Correct 83 ms 164716 KB Output is correct
28 Correct 69 ms 164812 KB Output is correct
29 Correct 55 ms 164744 KB Output is correct
30 Correct 160 ms 172376 KB Output is correct
31 Correct 158 ms 172372 KB Output is correct
32 Correct 169 ms 172628 KB Output is correct
33 Correct 110 ms 171508 KB Output is correct
34 Correct 137 ms 171804 KB Output is correct
35 Correct 146 ms 172368 KB Output is correct
36 Correct 132 ms 172372 KB Output is correct
37 Correct 143 ms 172492 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164692 KB Output is correct
2 Correct 69 ms 164944 KB Output is correct
3 Correct 59 ms 164784 KB Output is correct
4 Correct 77 ms 164692 KB Output is correct
5 Correct 68 ms 164816 KB Output is correct
6 Correct 57 ms 164952 KB Output is correct
7 Correct 82 ms 164644 KB Output is correct
8 Correct 54 ms 164696 KB Output is correct
9 Correct 55 ms 164688 KB Output is correct
10 Correct 89 ms 164692 KB Output is correct
11 Correct 54 ms 164692 KB Output is correct
12 Correct 87 ms 164948 KB Output is correct
13 Correct 69 ms 164668 KB Output is correct
14 Correct 54 ms 164692 KB Output is correct
15 Correct 88 ms 164652 KB Output is correct
16 Correct 102 ms 164796 KB Output is correct
17 Correct 97 ms 166372 KB Output is correct
18 Correct 93 ms 166644 KB Output is correct
19 Correct 67 ms 166484 KB Output is correct
20 Correct 95 ms 166228 KB Output is correct
21 Correct 70 ms 166232 KB Output is correct
22 Correct 63 ms 166484 KB Output is correct
23 Correct 61 ms 166168 KB Output is correct
24 Correct 58 ms 165556 KB Output is correct
25 Correct 160 ms 172376 KB Output is correct
26 Correct 158 ms 172372 KB Output is correct
27 Correct 169 ms 172628 KB Output is correct
28 Correct 110 ms 171508 KB Output is correct
29 Correct 137 ms 171804 KB Output is correct
30 Correct 146 ms 172368 KB Output is correct
31 Correct 132 ms 172372 KB Output is correct
32 Correct 143 ms 172492 KB Output is correct
33 Correct 58 ms 164684 KB Output is correct
34 Correct 80 ms 164696 KB Output is correct
35 Correct 83 ms 164716 KB Output is correct
36 Correct 69 ms 164812 KB Output is correct
37 Correct 55 ms 164744 KB Output is correct
38 Correct 948 ms 271064 KB Output is correct
39 Correct 1010 ms 271184 KB Output is correct
40 Correct 926 ms 271188 KB Output is correct
41 Correct 941 ms 271188 KB Output is correct
42 Correct 2338 ms 278868 KB Output is correct
43 Correct 2270 ms 279008 KB Output is correct
44 Correct 2341 ms 279348 KB Output is correct
45 Correct 2153 ms 277536 KB Output is correct
46 Correct 1008 ms 267316 KB Output is correct
47 Correct 1071 ms 267132 KB Output is correct
48 Correct 1891 ms 269032 KB Output is correct
49 Correct 2160 ms 278612 KB Output is correct
50 Correct 924 ms 221860 KB Output is correct
51 Correct 1018 ms 221712 KB Output is correct
52 Correct 2033 ms 270036 KB Output is correct
53 Correct 2062 ms 277200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 166584 KB Output is correct
2 Correct 80 ms 166384 KB Output is correct
3 Correct 60 ms 166368 KB Output is correct
4 Correct 78 ms 164692 KB Output is correct
5 Correct 68 ms 166572 KB Output is correct
6 Correct 83 ms 166572 KB Output is correct
7 Correct 90 ms 166436 KB Output is correct
8 Correct 75 ms 166532 KB Output is correct
9 Correct 67 ms 166576 KB Output is correct
10 Correct 81 ms 165156 KB Output is correct
11 Correct 89 ms 165792 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 164684 KB Output is correct
2 Correct 80 ms 164696 KB Output is correct
3 Correct 83 ms 164716 KB Output is correct
4 Correct 69 ms 164812 KB Output is correct
5 Correct 55 ms 164744 KB Output is correct
6 Correct 70 ms 164984 KB Output is correct
7 Execution timed out 5051 ms 954456 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164692 KB Output is correct
2 Correct 69 ms 164944 KB Output is correct
3 Correct 59 ms 164784 KB Output is correct
4 Correct 77 ms 164692 KB Output is correct
5 Correct 68 ms 164816 KB Output is correct
6 Correct 57 ms 164952 KB Output is correct
7 Correct 82 ms 164644 KB Output is correct
8 Correct 54 ms 164696 KB Output is correct
9 Correct 55 ms 164688 KB Output is correct
10 Correct 89 ms 164692 KB Output is correct
11 Correct 54 ms 164692 KB Output is correct
12 Correct 87 ms 164948 KB Output is correct
13 Correct 69 ms 164668 KB Output is correct
14 Correct 54 ms 164692 KB Output is correct
15 Correct 88 ms 164652 KB Output is correct
16 Correct 102 ms 164796 KB Output is correct
17 Correct 97 ms 166372 KB Output is correct
18 Correct 93 ms 166644 KB Output is correct
19 Correct 67 ms 166484 KB Output is correct
20 Correct 95 ms 166228 KB Output is correct
21 Correct 70 ms 166232 KB Output is correct
22 Correct 63 ms 166484 KB Output is correct
23 Correct 61 ms 166168 KB Output is correct
24 Correct 58 ms 165556 KB Output is correct
25 Correct 160 ms 172376 KB Output is correct
26 Correct 158 ms 172372 KB Output is correct
27 Correct 169 ms 172628 KB Output is correct
28 Correct 110 ms 171508 KB Output is correct
29 Correct 137 ms 171804 KB Output is correct
30 Correct 146 ms 172368 KB Output is correct
31 Correct 132 ms 172372 KB Output is correct
32 Correct 143 ms 172492 KB Output is correct
33 Correct 948 ms 271064 KB Output is correct
34 Correct 1010 ms 271184 KB Output is correct
35 Correct 926 ms 271188 KB Output is correct
36 Correct 941 ms 271188 KB Output is correct
37 Correct 2338 ms 278868 KB Output is correct
38 Correct 2270 ms 279008 KB Output is correct
39 Correct 2341 ms 279348 KB Output is correct
40 Correct 2153 ms 277536 KB Output is correct
41 Correct 1008 ms 267316 KB Output is correct
42 Correct 1071 ms 267132 KB Output is correct
43 Correct 1891 ms 269032 KB Output is correct
44 Correct 2160 ms 278612 KB Output is correct
45 Correct 924 ms 221860 KB Output is correct
46 Correct 1018 ms 221712 KB Output is correct
47 Correct 2033 ms 270036 KB Output is correct
48 Correct 2062 ms 277200 KB Output is correct
49 Correct 80 ms 166584 KB Output is correct
50 Correct 80 ms 166384 KB Output is correct
51 Correct 60 ms 166368 KB Output is correct
52 Correct 78 ms 164692 KB Output is correct
53 Correct 68 ms 166572 KB Output is correct
54 Correct 83 ms 166572 KB Output is correct
55 Correct 90 ms 166436 KB Output is correct
56 Correct 75 ms 166532 KB Output is correct
57 Correct 67 ms 166576 KB Output is correct
58 Correct 81 ms 165156 KB Output is correct
59 Correct 89 ms 165792 KB Output is correct
60 Correct 70 ms 164984 KB Output is correct
61 Execution timed out 5051 ms 954456 KB Time limit exceeded
62 Halted 0 ms 0 KB -