oj.uz

Submission #956923

# Submission time Handle Problem Language Result Execution time Memory
956923 2024-04-02T16:55:00 Z Macker Rectangles (IOI19_rect) C++17
50 / 100
 5000 ms 666668 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define int ll
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;

vector<int> get_last_big(vector<int> v){
	int n = v.size();
	vector<int> res(n, -1);
	stack<pii> s;
	s.push({INT_MAX, -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;
}

long long count_rectangles(vector<vector<signed>> v) {
	int n = v.size();
	int m = v[0].size();
	st.assign(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){
			st[i][j].mnx = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, m){
			st[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){
			st[i][j].mny = res[i];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(i, n){
			st[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) {
			st[x][y].on = true;
			int mxx, mnx, mxy, mny;
			mxx = st[x][y].mxx;
			mnx = st[x][y].mnx;
			mxy = st[x][y].mxy;
			mny = st[x][y].mny;
			if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue;

			bool f = 0;
			for (int i = mny + 1; i < mxy; i++){
				for (int j = mnx + 1; j < mxx; j++) {
					if(!st[i][j].on) {f = 1; break;}
					if(st[i][j].mnx < mnx) {f = 1; break;}
					if(st[i][j].mny < mny) {f = 1; break;}
					if(st[i][j].mxx > mxx) {f = 1; break;}
					if(st[i][j].mxy > mxy) {f = 1; break;}
				}
				if(f) break;
			}
			if(!f) res++;
		}
	}
	return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 164692 KB Output is correct
2 Correct 72 ms 164828 KB Output is correct
3 Correct 77 ms 164692 KB Output is correct
4 Correct 68 ms 164700 KB Output is correct
5 Correct 67 ms 164780 KB Output is correct
6 Correct 67 ms 164688 KB Output is correct
7 Correct 69 ms 164692 KB Output is correct
8 Correct 70 ms 164692 KB Output is correct
9 Correct 67 ms 164700 KB Output is correct
10 Correct 68 ms 164652 KB Output is correct
11 Correct 73 ms 164892 KB Output is correct
12 Correct 73 ms 164884 KB Output is correct
13 Correct 66 ms 164684 KB Output is correct
14 Correct 66 ms 164688 KB Output is correct
15 Correct 66 ms 164688 KB Output is correct
16 Correct 68 ms 164688 KB Output is correct
17 Correct 70 ms 164764 KB Output is correct
18 Correct 69 ms 164756 KB Output is correct
19 Correct 69 ms 164880 KB Output is correct
20 Correct 68 ms 164768 KB Output is correct
21 Correct 70 ms 164680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 164692 KB Output is correct
2 Correct 72 ms 164828 KB Output is correct
3 Correct 77 ms 164692 KB Output is correct
4 Correct 68 ms 164700 KB Output is correct
5 Correct 67 ms 164780 KB Output is correct
6 Correct 67 ms 164688 KB Output is correct
7 Correct 69 ms 164692 KB Output is correct
8 Correct 70 ms 164692 KB Output is correct
9 Correct 67 ms 164700 KB Output is correct
10 Correct 68 ms 164652 KB Output is correct
11 Correct 73 ms 164892 KB Output is correct
12 Correct 73 ms 164884 KB Output is correct
13 Correct 66 ms 164684 KB Output is correct
14 Correct 66 ms 164688 KB Output is correct
15 Correct 66 ms 164688 KB Output is correct
16 Correct 68 ms 164688 KB Output is correct
17 Correct 70 ms 164764 KB Output is correct
18 Correct 69 ms 164756 KB Output is correct
19 Correct 69 ms 164880 KB Output is correct
20 Correct 68 ms 164768 KB Output is correct
21 Correct 70 ms 164680 KB Output is correct
22 Correct 78 ms 165208 KB Output is correct
23 Correct 80 ms 165204 KB Output is correct
24 Correct 83 ms 165200 KB Output is correct
25 Correct 77 ms 165332 KB Output is correct
26 Correct 74 ms 165096 KB Output is correct
27 Correct 75 ms 165204 KB Output is correct
28 Correct 72 ms 165200 KB Output is correct
29 Correct 66 ms 164952 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 164692 KB Output is correct
2 Correct 72 ms 164828 KB Output is correct
3 Correct 77 ms 164692 KB Output is correct
4 Correct 68 ms 164700 KB Output is correct
5 Correct 67 ms 164780 KB Output is correct
6 Correct 67 ms 164688 KB Output is correct
7 Correct 69 ms 164692 KB Output is correct
8 Correct 70 ms 164692 KB Output is correct
9 Correct 67 ms 164700 KB Output is correct
10 Correct 68 ms 164652 KB Output is correct
11 Correct 73 ms 164892 KB Output is correct
12 Correct 73 ms 164884 KB Output is correct
13 Correct 66 ms 164684 KB Output is correct
14 Correct 66 ms 164688 KB Output is correct
15 Correct 66 ms 164688 KB Output is correct
16 Correct 68 ms 164688 KB Output is correct
17 Correct 78 ms 165208 KB Output is correct
18 Correct 80 ms 165204 KB Output is correct
19 Correct 83 ms 165200 KB Output is correct
20 Correct 77 ms 165332 KB Output is correct
21 Correct 74 ms 165096 KB Output is correct
22 Correct 75 ms 165204 KB Output is correct
23 Correct 72 ms 165200 KB Output is correct
24 Correct 66 ms 164952 KB Output is correct
25 Correct 70 ms 164764 KB Output is correct
26 Correct 69 ms 164756 KB Output is correct
27 Correct 69 ms 164880 KB Output is correct
28 Correct 68 ms 164768 KB Output is correct
29 Correct 70 ms 164680 KB Output is correct
30 Correct 592 ms 168080 KB Output is correct
31 Correct 617 ms 168136 KB Output is correct
32 Correct 606 ms 168020 KB Output is correct
33 Correct 70 ms 167492 KB Output is correct
34 Correct 74 ms 167760 KB Output is correct
35 Correct 88 ms 168020 KB Output is correct
36 Correct 84 ms 168116 KB Output is correct
37 Correct 93 ms 168368 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 164692 KB Output is correct
2 Correct 72 ms 164828 KB Output is correct
3 Correct 77 ms 164692 KB Output is correct
4 Correct 68 ms 164700 KB Output is correct
5 Correct 67 ms 164780 KB Output is correct
6 Correct 67 ms 164688 KB Output is correct
7 Correct 69 ms 164692 KB Output is correct
8 Correct 70 ms 164692 KB Output is correct
9 Correct 67 ms 164700 KB Output is correct
10 Correct 68 ms 164652 KB Output is correct
11 Correct 73 ms 164892 KB Output is correct
12 Correct 73 ms 164884 KB Output is correct
13 Correct 66 ms 164684 KB Output is correct
14 Correct 66 ms 164688 KB Output is correct
15 Correct 66 ms 164688 KB Output is correct
16 Correct 68 ms 164688 KB Output is correct
17 Correct 78 ms 165208 KB Output is correct
18 Correct 80 ms 165204 KB Output is correct
19 Correct 83 ms 165200 KB Output is correct
20 Correct 77 ms 165332 KB Output is correct
21 Correct 74 ms 165096 KB Output is correct
22 Correct 75 ms 165204 KB Output is correct
23 Correct 72 ms 165200 KB Output is correct
24 Correct 66 ms 164952 KB Output is correct
25 Correct 592 ms 168080 KB Output is correct
26 Correct 617 ms 168136 KB Output is correct
27 Correct 606 ms 168020 KB Output is correct
28 Correct 70 ms 167492 KB Output is correct
29 Correct 74 ms 167760 KB Output is correct
30 Correct 88 ms 168020 KB Output is correct
31 Correct 84 ms 168116 KB Output is correct
32 Correct 93 ms 168368 KB Output is correct
33 Correct 70 ms 164764 KB Output is correct
34 Correct 69 ms 164756 KB Output is correct
35 Correct 69 ms 164880 KB Output is correct
36 Correct 68 ms 164768 KB Output is correct
37 Correct 70 ms 164680 KB Output is correct
38 Correct 167 ms 202808 KB Output is correct
39 Correct 149 ms 202580 KB Output is correct
40 Correct 178 ms 202616 KB Output is correct
41 Correct 171 ms 202956 KB Output is correct
42 Execution timed out 5077 ms 206244 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 165272 KB Output is correct
2 Correct 72 ms 165288 KB Output is correct
3 Correct 66 ms 165460 KB Output is correct
4 Correct 67 ms 164696 KB Output is correct
5 Correct 75 ms 165204 KB Output is correct
6 Correct 73 ms 165272 KB Output is correct
7 Correct 73 ms 165468 KB Output is correct
8 Correct 70 ms 165340 KB Output is correct
9 Correct 70 ms 165204 KB Output is correct
10 Correct 69 ms 164948 KB Output is correct
11 Correct 72 ms 164984 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 164764 KB Output is correct
2 Correct 69 ms 164756 KB Output is correct
3 Correct 69 ms 164880 KB Output is correct
4 Correct 68 ms 164768 KB Output is correct
5 Correct 70 ms 164680 KB Output is correct
6 Correct 66 ms 164700 KB Output is correct
7 Correct 473 ms 366980 KB Output is correct
8 Correct 1142 ms 615648 KB Output is correct
9 Correct 1095 ms 617452 KB Output is correct
10 Correct 1058 ms 617796 KB Output is correct
11 Correct 472 ms 412620 KB Output is correct
12 Correct 887 ms 635436 KB Output is correct
13 Correct 912 ms 666668 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 164692 KB Output is correct
2 Correct 72 ms 164828 KB Output is correct
3 Correct 77 ms 164692 KB Output is correct
4 Correct 68 ms 164700 KB Output is correct
5 Correct 67 ms 164780 KB Output is correct
6 Correct 67 ms 164688 KB Output is correct
7 Correct 69 ms 164692 KB Output is correct
8 Correct 70 ms 164692 KB Output is correct
9 Correct 67 ms 164700 KB Output is correct
10 Correct 68 ms 164652 KB Output is correct
11 Correct 73 ms 164892 KB Output is correct
12 Correct 73 ms 164884 KB Output is correct
13 Correct 66 ms 164684 KB Output is correct
14 Correct 66 ms 164688 KB Output is correct
15 Correct 66 ms 164688 KB Output is correct
16 Correct 68 ms 164688 KB Output is correct
17 Correct 78 ms 165208 KB Output is correct
18 Correct 80 ms 165204 KB Output is correct
19 Correct 83 ms 165200 KB Output is correct
20 Correct 77 ms 165332 KB Output is correct
21 Correct 74 ms 165096 KB Output is correct
22 Correct 75 ms 165204 KB Output is correct
23 Correct 72 ms 165200 KB Output is correct
24 Correct 66 ms 164952 KB Output is correct
25 Correct 592 ms 168080 KB Output is correct
26 Correct 617 ms 168136 KB Output is correct
27 Correct 606 ms 168020 KB Output is correct
28 Correct 70 ms 167492 KB Output is correct
29 Correct 74 ms 167760 KB Output is correct
30 Correct 88 ms 168020 KB Output is correct
31 Correct 84 ms 168116 KB Output is correct
32 Correct 93 ms 168368 KB Output is correct
33 Correct 167 ms 202808 KB Output is correct
34 Correct 149 ms 202580 KB Output is correct
35 Correct 178 ms 202616 KB Output is correct
36 Correct 171 ms 202956 KB Output is correct
37 Execution timed out 5077 ms 206244 KB Time limit exceeded
38 Halted 0 ms 0 KB -