oj.uz

Submission #824999

# Submission time Handle Problem Language Result Execution time Memory
824999 2023-08-14T13:02:39 Z Ronin13 Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 805872 KB 
#include "rect.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back 
#define epb emplace_back
using namespace std;
const int nmax = 2501;

int c[nmax][nmax];// for min
int d[nmax][nmax];// for max

int st[nmax][nmax][13][2];

int get_max(int ind, int l, int r){
	int len = r - l + 1;
	int x = log2(len);
	return max(st[ind][l][x][0], st[ind][max(0,r - (1 << x) + 1)][x][0]);
}

int get_mn(int ind, int l, int r){
	int len = r - l + 1;
	int x = log2(len);
	return min(st[ind][l][x][1], st[ind][max(0, r - (1 << x) + 1)][x][1]);
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	for(int i = 0; i < n; i++){
		stack <int> st;
		for(int j = 0; j < m; j++){
			while(!st.empty()){
				if(a[i][st.top()] < a[i][j]) st.pop();
				else break;
			}
			if(!st.empty())
			d[i][j] = st.top();
			st.push(j);
		}
		while(!st.empty()){
			st.pop();
		}
		for(int j= m - 1 ;j >= 0; j--){
			while(!st.empty()){
				if(a[i][st.top()] < a[i][j]) st.pop();
				else break;
			}
			if(!st.empty()) c[i][j] = st.top();
			else c[i][j] = m - 1;
			st.push(j);
		}
	}
	for(int i = 0; i < m; i++){
		for(int j = n - 1; j >= 0; j--){
			st[i][j][0][0] = d[j][i], st[i][j][0][1] = c[j][i];
			for(int x =1; x < 13; x++){
				st[i][j][x][0] = max(st[i][j][x - 1][0], 
									st[i][min(j + (1 << (x - 1)), n - 1)][x - 1][0]);
				st[i][j][x][1] = min(st[i][j][x - 1][1], 
									st[i][min(j + (1 << (x - 1)), n - 1)][x - 1][1]);
			}
		}
	}
	vector <pii> p[m + 1];
	for(int j = 0; j < m; j++){
		int l[n + 1], r[n + 1];
		fill(l , l + n + 1, -1);
		fill(r, r + n + 1, n + 1);
		stack <int> st;
		for(int i = 0; i < n; i++){
			while(!st.empty()){
				if(a[st.top()][j] > a[i][j]) break;
				else st.pop();
			}
			if(!st.empty()) l[i] = st.top();
			st.push(i);
		}
		while(!st.empty()) st.pop();
		for(int i = n - 1; i >= 0; i--){
			while(!st.empty()){
				if(a[st.top()][j] > a[i][j]) break;
				else st.pop();
			}
			if(!st.empty()) r[i] = st.top();
			st.push(i);
		}
		for(int i = 0; i < n; i++){
			if(l[i] != -1  && r[i] != n + 1)
				p[j].pb({l[i] + 1, r[i] - 1});
		}
		sort(p[j].begin(), p[j].end());
		p[j].erase(unique(p[j].begin(), p[j].end()), p[j].end());
	}
	
	int ans = 0;
	for(int i = 1; i < m - 1; i++){
		vector <pii> cur = p[i];
		vector <pii> nw;
		for(int j = i; j < m - 1; j++){
			
			int inda = 0, indb = 0;
			while(inda < cur.size() && indb < p[j].size()){
				if(cur[inda] == p[j][indb]) nw.pb(cur[inda]), inda++, indb++;
				else{
					if(cur[inda] < p[j][indb]) inda++;
					else indb++;
				}
			}
			swap(nw, cur);
			nw.clear();
			for(auto to : cur){
				//if(i == 3 && j == 3) cout << to.f << ' ' << to.s << "\n";
				int L = to.f, R = to.s;
				if(get_max(j + 1, L, R) >= i) continue;
			//	if(i == 3 && j == 3) cout << to.f << ' ' << to.s << "\n";
			//	cout << get_mn(i - 1, L, R) << "\n";
				if(get_mn(i - 1, L, R) <= j) continue;
			//	cout << i << ' ' << j << ' ' << L << ' ' << R << "\n";
				ans++;
			}
		}
	}
	return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:106:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    while(inda < cur.size() && indb < p[j].size()){
      |          ~~~~~^~~~~~~~~~~~
rect.cpp:106:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    while(inda < cur.size() && indb < p[j].size()){
      |                               ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 556 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 820 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 0 ms 304 KB Output is correct
19 Correct 1 ms 812 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 0 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 556 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 820 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 0 ms 304 KB Output is correct
19 Correct 1 ms 812 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 6 ms 2132 KB Output is correct
23 Correct 6 ms 2132 KB Output is correct
24 Correct 6 ms 2132 KB Output is correct
25 Correct 2 ms 2132 KB Output is correct
26 Correct 3 ms 2084 KB Output is correct
27 Correct 2 ms 2132 KB Output is correct
28 Correct 2 ms 2132 KB Output is correct
29 Correct 1 ms 1492 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 556 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 820 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 6 ms 2132 KB Output is correct
18 Correct 6 ms 2132 KB Output is correct
19 Correct 6 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 3 ms 2084 KB Output is correct
22 Correct 2 ms 2132 KB Output is correct
23 Correct 2 ms 2132 KB Output is correct
24 Correct 1 ms 1492 KB Output is correct
25 Correct 1 ms 308 KB Output is correct
26 Correct 0 ms 304 KB Output is correct
27 Correct 1 ms 812 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 74 ms 8040 KB Output is correct
31 Correct 69 ms 7944 KB Output is correct
32 Correct 73 ms 8044 KB Output is correct
33 Correct 8 ms 7892 KB Output is correct
34 Correct 12 ms 8020 KB Output is correct
35 Correct 13 ms 8020 KB Output is correct
36 Correct 14 ms 8020 KB Output is correct
37 Correct 13 ms 7944 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 556 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 820 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 6 ms 2132 KB Output is correct
18 Correct 6 ms 2132 KB Output is correct
19 Correct 6 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 3 ms 2084 KB Output is correct
22 Correct 2 ms 2132 KB Output is correct
23 Correct 2 ms 2132 KB Output is correct
24 Correct 1 ms 1492 KB Output is correct
25 Correct 74 ms 8040 KB Output is correct
26 Correct 69 ms 7944 KB Output is correct
27 Correct 73 ms 8044 KB Output is correct
28 Correct 8 ms 7892 KB Output is correct
29 Correct 12 ms 8020 KB Output is correct
30 Correct 13 ms 8020 KB Output is correct
31 Correct 14 ms 8020 KB Output is correct
32 Correct 13 ms 7944 KB Output is correct
33 Correct 1 ms 308 KB Output is correct
34 Correct 0 ms 304 KB Output is correct
35 Correct 1 ms 812 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 79 ms 68528 KB Output is correct
39 Correct 76 ms 69500 KB Output is correct
40 Correct 77 ms 68572 KB Output is correct
41 Correct 77 ms 69444 KB Output is correct
42 Correct 3521 ms 72248 KB Output is correct
43 Correct 3573 ms 75320 KB Output is correct
44 Correct 3525 ms 75676 KB Output is correct
45 Correct 3263 ms 71552 KB Output is correct
46 Correct 96 ms 70192 KB Output is correct
47 Correct 110 ms 70180 KB Output is correct
48 Correct 145 ms 74104 KB Output is correct
49 Correct 148 ms 75724 KB Output is correct
50 Correct 72 ms 40948 KB Output is correct
51 Correct 71 ms 39508 KB Output is correct
52 Correct 325 ms 74892 KB Output is correct
53 Correct 382 ms 75820 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12628 KB Output is correct
2 Correct 38 ms 10708 KB Output is correct
3 Correct 16 ms 12520 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 12 ms 12576 KB Output is correct
6 Correct 12 ms 12576 KB Output is correct
7 Correct 12 ms 12584 KB Output is correct
8 Correct 13 ms 12500 KB Output is correct
9 Correct 16 ms 12572 KB Output is correct
10 Correct 13 ms 11860 KB Output is correct
11 Correct 12 ms 12240 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 812 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 584 ms 367120 KB Output is correct
8 Correct 1421 ms 768856 KB Output is correct
9 Correct 1339 ms 769696 KB Output is correct
10 Correct 1365 ms 769940 KB Output is correct
11 Correct 458 ms 373584 KB Output is correct
12 Correct 842 ms 692844 KB Output is correct
13 Correct 917 ms 735468 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 556 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 820 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 6 ms 2132 KB Output is correct
18 Correct 6 ms 2132 KB Output is correct
19 Correct 6 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 3 ms 2084 KB Output is correct
22 Correct 2 ms 2132 KB Output is correct
23 Correct 2 ms 2132 KB Output is correct
24 Correct 1 ms 1492 KB Output is correct
25 Correct 74 ms 8040 KB Output is correct
26 Correct 69 ms 7944 KB Output is correct
27 Correct 73 ms 8044 KB Output is correct
28 Correct 8 ms 7892 KB Output is correct
29 Correct 12 ms 8020 KB Output is correct
30 Correct 13 ms 8020 KB Output is correct
31 Correct 14 ms 8020 KB Output is correct
32 Correct 13 ms 7944 KB Output is correct
33 Correct 79 ms 68528 KB Output is correct
34 Correct 76 ms 69500 KB Output is correct
35 Correct 77 ms 68572 KB Output is correct
36 Correct 77 ms 69444 KB Output is correct
37 Correct 3521 ms 72248 KB Output is correct
38 Correct 3573 ms 75320 KB Output is correct
39 Correct 3525 ms 75676 KB Output is correct
40 Correct 3263 ms 71552 KB Output is correct
41 Correct 96 ms 70192 KB Output is correct
42 Correct 110 ms 70180 KB Output is correct
43 Correct 145 ms 74104 KB Output is correct
44 Correct 148 ms 75724 KB Output is correct
45 Correct 72 ms 40948 KB Output is correct
46 Correct 71 ms 39508 KB Output is correct
47 Correct 325 ms 74892 KB Output is correct
48 Correct 382 ms 75820 KB Output is correct
49 Correct 59 ms 12628 KB Output is correct
50 Correct 38 ms 10708 KB Output is correct
51 Correct 16 ms 12520 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 12 ms 12576 KB Output is correct
54 Correct 12 ms 12576 KB Output is correct
55 Correct 12 ms 12584 KB Output is correct
56 Correct 13 ms 12500 KB Output is correct
57 Correct 16 ms 12572 KB Output is correct
58 Correct 13 ms 11860 KB Output is correct
59 Correct 12 ms 12240 KB Output is correct
60 Correct 0 ms 432 KB Output is correct
61 Correct 584 ms 367120 KB Output is correct
62 Correct 1421 ms 768856 KB Output is correct
63 Correct 1339 ms 769696 KB Output is correct
64 Correct 1365 ms 769940 KB Output is correct
65 Correct 458 ms 373584 KB Output is correct
66 Correct 842 ms 692844 KB Output is correct
67 Correct 917 ms 735468 KB Output is correct
68 Correct 1 ms 308 KB Output is correct
69 Correct 0 ms 304 KB Output is correct
70 Correct 1 ms 812 KB Output is correct
71 Correct 1 ms 596 KB Output is correct
72 Correct 0 ms 340 KB Output is correct
73 Correct 1197 ms 768144 KB Output is correct
74 Correct 1201 ms 775344 KB Output is correct
75 Correct 1202 ms 771096 KB Output is correct
76 Correct 1193 ms 775520 KB Output is correct
77 Execution timed out 5139 ms 805872 KB Time limit exceeded
78 Halted 0 ms 0 KB -