oj.uz

Submission #1047436

# Submission time Handle Problem Language Result Execution time Memory
1047436 2024-08-07T13:01:26 Z fuad27 Rectangles (IOI19_rect) C++17
59 / 100
 3516 ms 1048576 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2510;
int n,m;
vector<pair<int,int>> gdr[N];
vector<pair<int,int>> gdc[N];

struct Side {
	int r1, r2, c1, c2;
};
vector<Side> hsides[N][N];
vector<Side> vsides[N][N];
vector<pair<int,int>> swp[N];
long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for(int i = 0;i<n;i++) {
		vector<int> stk;
		for(int j = 0;j<m;j++) {
			while(stk.size() and a[i][stk.back()] < a[i][j]){
				stk.pop_back();
			}
			if(stk.size()) {
				gdr[i].push_back({stk.back(), j});
			}
			stk.push_back(j);
		}
		stk.clear();
		for(int j = m-1;j>=0;j--) {
			while(stk.size() and a[i][stk.back()] < a[i][j])stk.pop_back();
			if(stk.size()) {
				if(a[i][j] != a[i][stk.back()])
					gdr[i].push_back({j, stk.back()});
			}
			stk.push_back(j);
		}
		sort(gdr[i].begin(), gdr[i].end());
	}
	for(int i = 0;i<m;i++) {
		vector<int> stk;
		for(int j = 0;j<n;j++) {
			while(stk.size() and a[stk.back()][i] < a[j][i]){
				stk.pop_back();
			}
			if(stk.size()) {
				gdc[i].push_back({stk.back(), j});
			}
			stk.push_back(j);
		}
		stk.clear();
		for(int j = n-1;j>=0;j--) {
			while(stk.size() and a[stk.back()][i] < a[j][i])stk.pop_back();
			if(stk.size()) {
				gdc[i].push_back({j, stk.back()});
			}
			stk.push_back(j);
		}
		sort(gdc[i].begin(), gdc[i].end());
		gdc[i].erase(unique(gdc[i].begin(), gdc[i].end()), gdc[i].end());
	}
	for(int i = 0;i<n;i++) {
		for(auto pr:gdr[i]) {
			if(i!=n-1 and (*lower_bound(gdr[i+1].begin(), gdr[i+1].end(), pr)) == pr)continue;
			Side seg;
			seg.r1 = pr.first;
			seg.r2 = pr.second;
			seg.c2 = i;
			for(int j = i;j>=0;j--){
				auto it = (lower_bound(gdr[j].begin(), gdr[j].end(), pr));
				if(it == gdr[j].end())break;
				if((*it)!=pr)break;
				seg.c1=j;
			}
			seg.c1--;
			seg.c2++;
			seg.c1=max(seg.c1, 0);
			seg.c2=min(seg.c2, n-1);
			for(int j = seg.c1;j<=seg.c2;j++) {
				hsides[j][seg.r2].push_back(seg);
			}
		}
	}





	for(int i = 0;i<m;i++) {
		for(auto pr:gdc[i]) {
			if(i!=m-1 and (*lower_bound(gdc[i+1].begin(), gdc[i+1].end(), pr)) == pr)continue;
			Side seg;
			seg.r1 = pr.first;
			seg.r2 = pr.second;
			seg.c2 = i;
			for(int j = i;j>=0;j--){
				auto it = (lower_bound(gdc[j].begin(), gdc[j].end(), pr));
				if(it == gdc[j].end())break;
				if((*it)!=pr)break;
				seg.c1=j;
			}
			seg.c1--;
			seg.c2++;
			seg.c1=max(seg.c1, 0);
			seg.c2=min(seg.c2, m-1);
			for(int j = seg.c1;j<=seg.c2;j++) {
				vsides[seg.r2][j].push_back(seg);
			}
		}
	}


	long long ans=0;
	for(int i = 0;i<n;i++) {
		for(int j = 0;j<m;j++) {
			int tmp=0;
			for(auto k:vsides[i][j]) {
				if(k.r1+1 == k.r2)break;
				for(auto k2:hsides[i][j]) {
					if(k2.r1+1 == k2.r2)break;
					if(k2.r1 >= k.c1 and k2.c1 <= k.r1) {
//						cout << i << " " << k2.r1 << " " <<  k.r1 << " " << j <<  endl;
						ans++;
						tmp++;
					}

				}
			}
//			cout << i << " " << j << " " << tmp << endl;
		}
	}
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 296280 KB Output is correct
2 Correct 40 ms 296540 KB Output is correct
3 Correct 40 ms 296540 KB Output is correct
4 Correct 43 ms 296552 KB Output is correct
5 Correct 39 ms 296528 KB Output is correct
6 Correct 41 ms 296492 KB Output is correct
7 Correct 40 ms 296440 KB Output is correct
8 Correct 41 ms 296464 KB Output is correct
9 Correct 41 ms 296540 KB Output is correct
10 Correct 44 ms 296488 KB Output is correct
11 Correct 42 ms 296552 KB Output is correct
12 Correct 41 ms 296540 KB Output is correct
13 Correct 44 ms 296448 KB Output is correct
14 Correct 43 ms 296284 KB Output is correct
15 Correct 40 ms 296276 KB Output is correct
16 Correct 40 ms 296284 KB Output is correct
17 Correct 41 ms 296484 KB Output is correct
18 Correct 45 ms 296420 KB Output is correct
19 Correct 41 ms 296540 KB Output is correct
20 Correct 39 ms 296536 KB Output is correct
21 Correct 40 ms 296504 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 296280 KB Output is correct
2 Correct 40 ms 296540 KB Output is correct
3 Correct 40 ms 296540 KB Output is correct
4 Correct 43 ms 296552 KB Output is correct
5 Correct 39 ms 296528 KB Output is correct
6 Correct 41 ms 296492 KB Output is correct
7 Correct 40 ms 296440 KB Output is correct
8 Correct 41 ms 296464 KB Output is correct
9 Correct 41 ms 296540 KB Output is correct
10 Correct 44 ms 296488 KB Output is correct
11 Correct 42 ms 296552 KB Output is correct
12 Correct 41 ms 296540 KB Output is correct
13 Correct 44 ms 296448 KB Output is correct
14 Correct 43 ms 296284 KB Output is correct
15 Correct 40 ms 296276 KB Output is correct
16 Correct 40 ms 296284 KB Output is correct
17 Correct 41 ms 296484 KB Output is correct
18 Correct 45 ms 296420 KB Output is correct
19 Correct 41 ms 296540 KB Output is correct
20 Correct 39 ms 296536 KB Output is correct
21 Correct 40 ms 296504 KB Output is correct
22 Correct 46 ms 297556 KB Output is correct
23 Correct 42 ms 297544 KB Output is correct
24 Correct 42 ms 297556 KB Output is correct
25 Correct 45 ms 297296 KB Output is correct
26 Correct 45 ms 297812 KB Output is correct
27 Correct 45 ms 297724 KB Output is correct
28 Correct 46 ms 297812 KB Output is correct
29 Correct 43 ms 296924 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 296280 KB Output is correct
2 Correct 40 ms 296540 KB Output is correct
3 Correct 40 ms 296540 KB Output is correct
4 Correct 43 ms 296552 KB Output is correct
5 Correct 39 ms 296528 KB Output is correct
6 Correct 41 ms 296492 KB Output is correct
7 Correct 40 ms 296440 KB Output is correct
8 Correct 41 ms 296464 KB Output is correct
9 Correct 41 ms 296540 KB Output is correct
10 Correct 44 ms 296488 KB Output is correct
11 Correct 42 ms 296552 KB Output is correct
12 Correct 41 ms 296540 KB Output is correct
13 Correct 44 ms 296448 KB Output is correct
14 Correct 43 ms 296284 KB Output is correct
15 Correct 40 ms 296276 KB Output is correct
16 Correct 40 ms 296284 KB Output is correct
17 Correct 46 ms 297556 KB Output is correct
18 Correct 42 ms 297544 KB Output is correct
19 Correct 42 ms 297556 KB Output is correct
20 Correct 45 ms 297296 KB Output is correct
21 Correct 45 ms 297812 KB Output is correct
22 Correct 45 ms 297724 KB Output is correct
23 Correct 46 ms 297812 KB Output is correct
24 Correct 43 ms 296924 KB Output is correct
25 Correct 41 ms 296484 KB Output is correct
26 Correct 45 ms 296420 KB Output is correct
27 Correct 41 ms 296540 KB Output is correct
28 Correct 39 ms 296536 KB Output is correct
29 Correct 40 ms 296504 KB Output is correct
30 Correct 52 ms 302328 KB Output is correct
31 Correct 53 ms 302420 KB Output is correct
32 Correct 52 ms 302400 KB Output is correct
33 Correct 66 ms 302416 KB Output is correct
34 Correct 76 ms 305052 KB Output is correct
35 Correct 78 ms 305236 KB Output is correct
36 Correct 75 ms 304364 KB Output is correct
37 Correct 77 ms 304468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 296280 KB Output is correct
2 Correct 40 ms 296540 KB Output is correct
3 Correct 40 ms 296540 KB Output is correct
4 Correct 43 ms 296552 KB Output is correct
5 Correct 39 ms 296528 KB Output is correct
6 Correct 41 ms 296492 KB Output is correct
7 Correct 40 ms 296440 KB Output is correct
8 Correct 41 ms 296464 KB Output is correct
9 Correct 41 ms 296540 KB Output is correct
10 Correct 44 ms 296488 KB Output is correct
11 Correct 42 ms 296552 KB Output is correct
12 Correct 41 ms 296540 KB Output is correct
13 Correct 44 ms 296448 KB Output is correct
14 Correct 43 ms 296284 KB Output is correct
15 Correct 40 ms 296276 KB Output is correct
16 Correct 40 ms 296284 KB Output is correct
17 Correct 46 ms 297556 KB Output is correct
18 Correct 42 ms 297544 KB Output is correct
19 Correct 42 ms 297556 KB Output is correct
20 Correct 45 ms 297296 KB Output is correct
21 Correct 45 ms 297812 KB Output is correct
22 Correct 45 ms 297724 KB Output is correct
23 Correct 46 ms 297812 KB Output is correct
24 Correct 43 ms 296924 KB Output is correct
25 Correct 52 ms 302328 KB Output is correct
26 Correct 53 ms 302420 KB Output is correct
27 Correct 52 ms 302400 KB Output is correct
28 Correct 66 ms 302416 KB Output is correct
29 Correct 76 ms 305052 KB Output is correct
30 Correct 78 ms 305236 KB Output is correct
31 Correct 75 ms 304364 KB Output is correct
32 Correct 77 ms 304468 KB Output is correct
33 Correct 41 ms 296484 KB Output is correct
34 Correct 45 ms 296420 KB Output is correct
35 Correct 41 ms 296540 KB Output is correct
36 Correct 39 ms 296536 KB Output is correct
37 Correct 40 ms 296504 KB Output is correct
38 Correct 310 ms 378964 KB Output is correct
39 Correct 239 ms 373596 KB Output is correct
40 Correct 254 ms 374100 KB Output is correct
41 Correct 238 ms 369236 KB Output is correct
42 Correct 221 ms 373452 KB Output is correct
43 Correct 215 ms 373580 KB Output is correct
44 Correct 223 ms 373452 KB Output is correct
45 Correct 224 ms 369232 KB Output is correct
46 Correct 348 ms 359764 KB Output is correct
47 Correct 415 ms 368212 KB Output is correct
48 Correct 600 ms 406356 KB Output is correct
49 Correct 609 ms 407180 KB Output is correct
50 Correct 307 ms 351824 KB Output is correct
51 Correct 326 ms 351568 KB Output is correct
52 Correct 548 ms 394836 KB Output is correct
53 Correct 564 ms 395272 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 297368 KB Output is correct
2 Correct 43 ms 297052 KB Output is correct
3 Correct 41 ms 297128 KB Output is correct
4 Correct 40 ms 296280 KB Output is correct
5 Correct 50 ms 297556 KB Output is correct
6 Correct 44 ms 297300 KB Output is correct
7 Correct 44 ms 297300 KB Output is correct
8 Correct 44 ms 297300 KB Output is correct
9 Correct 43 ms 297296 KB Output is correct
10 Correct 42 ms 296532 KB Output is correct
11 Correct 44 ms 296872 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 296484 KB Output is correct
2 Correct 45 ms 296420 KB Output is correct
3 Correct 41 ms 296540 KB Output is correct
4 Correct 39 ms 296536 KB Output is correct
5 Correct 40 ms 296504 KB Output is correct
6 Correct 39 ms 296276 KB Output is correct
7 Correct 2107 ms 660388 KB Output is correct
8 Runtime error 3516 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 296280 KB Output is correct
2 Correct 40 ms 296540 KB Output is correct
3 Correct 40 ms 296540 KB Output is correct
4 Correct 43 ms 296552 KB Output is correct
5 Correct 39 ms 296528 KB Output is correct
6 Correct 41 ms 296492 KB Output is correct
7 Correct 40 ms 296440 KB Output is correct
8 Correct 41 ms 296464 KB Output is correct
9 Correct 41 ms 296540 KB Output is correct
10 Correct 44 ms 296488 KB Output is correct
11 Correct 42 ms 296552 KB Output is correct
12 Correct 41 ms 296540 KB Output is correct
13 Correct 44 ms 296448 KB Output is correct
14 Correct 43 ms 296284 KB Output is correct
15 Correct 40 ms 296276 KB Output is correct
16 Correct 40 ms 296284 KB Output is correct
17 Correct 46 ms 297556 KB Output is correct
18 Correct 42 ms 297544 KB Output is correct
19 Correct 42 ms 297556 KB Output is correct
20 Correct 45 ms 297296 KB Output is correct
21 Correct 45 ms 297812 KB Output is correct
22 Correct 45 ms 297724 KB Output is correct
23 Correct 46 ms 297812 KB Output is correct
24 Correct 43 ms 296924 KB Output is correct
25 Correct 52 ms 302328 KB Output is correct
26 Correct 53 ms 302420 KB Output is correct
27 Correct 52 ms 302400 KB Output is correct
28 Correct 66 ms 302416 KB Output is correct
29 Correct 76 ms 305052 KB Output is correct
30 Correct 78 ms 305236 KB Output is correct
31 Correct 75 ms 304364 KB Output is correct
32 Correct 77 ms 304468 KB Output is correct
33 Correct 310 ms 378964 KB Output is correct
34 Correct 239 ms 373596 KB Output is correct
35 Correct 254 ms 374100 KB Output is correct
36 Correct 238 ms 369236 KB Output is correct
37 Correct 221 ms 373452 KB Output is correct
38 Correct 215 ms 373580 KB Output is correct
39 Correct 223 ms 373452 KB Output is correct
40 Correct 224 ms 369232 KB Output is correct
41 Correct 348 ms 359764 KB Output is correct
42 Correct 415 ms 368212 KB Output is correct
43 Correct 600 ms 406356 KB Output is correct
44 Correct 609 ms 407180 KB Output is correct
45 Correct 307 ms 351824 KB Output is correct
46 Correct 326 ms 351568 KB Output is correct
47 Correct 548 ms 394836 KB Output is correct
48 Correct 564 ms 395272 KB Output is correct
49 Correct 43 ms 297368 KB Output is correct
50 Correct 43 ms 297052 KB Output is correct
51 Correct 41 ms 297128 KB Output is correct
52 Correct 40 ms 296280 KB Output is correct
53 Correct 50 ms 297556 KB Output is correct
54 Correct 44 ms 297300 KB Output is correct
55 Correct 44 ms 297300 KB Output is correct
56 Correct 44 ms 297300 KB Output is correct
57 Correct 43 ms 297296 KB Output is correct
58 Correct 42 ms 296532 KB Output is correct
59 Correct 44 ms 296872 KB Output is correct
60 Correct 39 ms 296276 KB Output is correct
61 Correct 2107 ms 660388 KB Output is correct
62 Runtime error 3516 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -