oj.uz

Submission #1047494

# Submission time Handle Problem Language Result Execution time Memory
1047494 2024-08-07T13:38:22 Z fuad27 Rectangles (IOI19_rect) C++17
72 / 100
 4139 ms 1048576 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
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<pair<int,int>> hsides[N][N];
vector<pair<int,int>> vsides[N][N];
vector<pair<int,int>> swp[N];


int fen[N];
void upd(int at, int add) {
	at++;
	while(at) {
		fen[at]+=add;
		at-=at&(-at);
	}
}
int qry(int at) {
	at++;
	int sum=0;
	while(at<N) {
		sum+=fen[at];
		at+=at&(-at);
	}
	return sum;
}
			

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());
	}
	Side seg;
	for(int i = 0;i<n;i++) {
		for(auto pr:gdr[i]) {

			if(pr.first +1 == pr.second)continue;
			if(i!=n-1 and (*lower_bound(gdr[i+1].begin(), gdr[i+1].end(), pr)) == pr)continue;
			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(pair<int,int>(seg.c1, seg.r1));
			}
		}
	}
	for(int i = 0;i<m;i++) {
		for(auto pr:gdc[i]) {
			if(pr.first +1 == pr.second)continue;
			if(i!=m-1 and (*lower_bound(gdc[i+1].begin(), gdc[i+1].end(), pr)) == pr)continue;
			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(pair<int,int>(seg.r1, seg.c1));
			}
		}
	}


	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]) {
//				for(auto k2:hsides[i][j]) {
//					if(k2.second >= k.second and k2.first <= k.first) {
//						ans++;
//						tmp++;
//					}
//				}
//			}
			sort(vsides[i][j].begin(), vsides[i][j].end());
			sort(hsides[i][j].begin(), hsides[i][j].end());
			int p1 = 0;
			for(auto k:vsides[i][j]) {
				while(p1 < (int)hsides[i][j].size() and hsides[i][j][p1].first <= k.first) {
					upd(hsides[i][j][p1++].second, 1);
				}
				ans+=qry(k.second);
			}
			while(p1 < (int)hsides[i][j].size()) {
				upd(hsides[i][j][p1++].second, 1);
			}
			for(auto k:hsides[i][j]) {
				upd(k.second, -1);
			}
		}
	}
	return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:135:8: warning: unused variable 'tmp' [-Wunused-variable]
  135 |    int tmp=0;
      |        ^~~
rect.cpp:99:10: warning: 'seg.Side::c1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |    seg.c1--;
      |    ~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 296468 KB Output is correct
2 Correct 70 ms 296532 KB Output is correct
3 Correct 56 ms 296532 KB Output is correct
4 Correct 61 ms 296432 KB Output is correct
5 Correct 51 ms 296460 KB Output is correct
6 Correct 54 ms 296404 KB Output is correct
7 Correct 47 ms 296460 KB Output is correct
8 Correct 42 ms 296516 KB Output is correct
9 Correct 45 ms 296432 KB Output is correct
10 Correct 42 ms 296536 KB Output is correct
11 Correct 45 ms 296532 KB Output is correct
12 Correct 49 ms 296580 KB Output is correct
13 Correct 44 ms 296276 KB Output is correct
14 Correct 75 ms 296484 KB Output is correct
15 Correct 74 ms 296500 KB Output is correct
16 Correct 47 ms 296440 KB Output is correct
17 Correct 53 ms 296428 KB Output is correct
18 Correct 54 ms 296320 KB Output is correct
19 Correct 52 ms 296536 KB Output is correct
20 Correct 43 ms 296436 KB Output is correct
21 Correct 53 ms 296276 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 296468 KB Output is correct
2 Correct 70 ms 296532 KB Output is correct
3 Correct 56 ms 296532 KB Output is correct
4 Correct 61 ms 296432 KB Output is correct
5 Correct 51 ms 296460 KB Output is correct
6 Correct 54 ms 296404 KB Output is correct
7 Correct 47 ms 296460 KB Output is correct
8 Correct 42 ms 296516 KB Output is correct
9 Correct 45 ms 296432 KB Output is correct
10 Correct 42 ms 296536 KB Output is correct
11 Correct 45 ms 296532 KB Output is correct
12 Correct 49 ms 296580 KB Output is correct
13 Correct 44 ms 296276 KB Output is correct
14 Correct 75 ms 296484 KB Output is correct
15 Correct 74 ms 296500 KB Output is correct
16 Correct 47 ms 296440 KB Output is correct
17 Correct 53 ms 296428 KB Output is correct
18 Correct 54 ms 296320 KB Output is correct
19 Correct 52 ms 296536 KB Output is correct
20 Correct 43 ms 296436 KB Output is correct
21 Correct 53 ms 296276 KB Output is correct
22 Correct 80 ms 296952 KB Output is correct
23 Correct 77 ms 297044 KB Output is correct
24 Correct 111 ms 296928 KB Output is correct
25 Correct 60 ms 297044 KB Output is correct
26 Correct 68 ms 297196 KB Output is correct
27 Correct 50 ms 297172 KB Output is correct
28 Correct 120 ms 297252 KB Output is correct
29 Correct 80 ms 296808 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 296468 KB Output is correct
2 Correct 70 ms 296532 KB Output is correct
3 Correct 56 ms 296532 KB Output is correct
4 Correct 61 ms 296432 KB Output is correct
5 Correct 51 ms 296460 KB Output is correct
6 Correct 54 ms 296404 KB Output is correct
7 Correct 47 ms 296460 KB Output is correct
8 Correct 42 ms 296516 KB Output is correct
9 Correct 45 ms 296432 KB Output is correct
10 Correct 42 ms 296536 KB Output is correct
11 Correct 45 ms 296532 KB Output is correct
12 Correct 49 ms 296580 KB Output is correct
13 Correct 44 ms 296276 KB Output is correct
14 Correct 75 ms 296484 KB Output is correct
15 Correct 74 ms 296500 KB Output is correct
16 Correct 47 ms 296440 KB Output is correct
17 Correct 80 ms 296952 KB Output is correct
18 Correct 77 ms 297044 KB Output is correct
19 Correct 111 ms 296928 KB Output is correct
20 Correct 60 ms 297044 KB Output is correct
21 Correct 68 ms 297196 KB Output is correct
22 Correct 50 ms 297172 KB Output is correct
23 Correct 120 ms 297252 KB Output is correct
24 Correct 80 ms 296808 KB Output is correct
25 Correct 53 ms 296428 KB Output is correct
26 Correct 54 ms 296320 KB Output is correct
27 Correct 52 ms 296536 KB Output is correct
28 Correct 43 ms 296436 KB Output is correct
29 Correct 53 ms 296276 KB Output is correct
30 Correct 67 ms 299196 KB Output is correct
31 Correct 66 ms 299208 KB Output is correct
32 Correct 86 ms 299264 KB Output is correct
33 Correct 120 ms 300172 KB Output is correct
34 Correct 106 ms 301396 KB Output is correct
35 Correct 96 ms 301492 KB Output is correct
36 Correct 102 ms 301140 KB Output is correct
37 Correct 105 ms 301004 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 296468 KB Output is correct
2 Correct 70 ms 296532 KB Output is correct
3 Correct 56 ms 296532 KB Output is correct
4 Correct 61 ms 296432 KB Output is correct
5 Correct 51 ms 296460 KB Output is correct
6 Correct 54 ms 296404 KB Output is correct
7 Correct 47 ms 296460 KB Output is correct
8 Correct 42 ms 296516 KB Output is correct
9 Correct 45 ms 296432 KB Output is correct
10 Correct 42 ms 296536 KB Output is correct
11 Correct 45 ms 296532 KB Output is correct
12 Correct 49 ms 296580 KB Output is correct
13 Correct 44 ms 296276 KB Output is correct
14 Correct 75 ms 296484 KB Output is correct
15 Correct 74 ms 296500 KB Output is correct
16 Correct 47 ms 296440 KB Output is correct
17 Correct 80 ms 296952 KB Output is correct
18 Correct 77 ms 297044 KB Output is correct
19 Correct 111 ms 296928 KB Output is correct
20 Correct 60 ms 297044 KB Output is correct
21 Correct 68 ms 297196 KB Output is correct
22 Correct 50 ms 297172 KB Output is correct
23 Correct 120 ms 297252 KB Output is correct
24 Correct 80 ms 296808 KB Output is correct
25 Correct 67 ms 299196 KB Output is correct
26 Correct 66 ms 299208 KB Output is correct
27 Correct 86 ms 299264 KB Output is correct
28 Correct 120 ms 300172 KB Output is correct
29 Correct 106 ms 301396 KB Output is correct
30 Correct 96 ms 301492 KB Output is correct
31 Correct 102 ms 301140 KB Output is correct
32 Correct 105 ms 301004 KB Output is correct
33 Correct 53 ms 296428 KB Output is correct
34 Correct 54 ms 296320 KB Output is correct
35 Correct 52 ms 296536 KB Output is correct
36 Correct 43 ms 296436 KB Output is correct
37 Correct 53 ms 296276 KB Output is correct
38 Correct 243 ms 332884 KB Output is correct
39 Correct 191 ms 335660 KB Output is correct
40 Correct 203 ms 335880 KB Output is correct
41 Correct 207 ms 338732 KB Output is correct
42 Correct 254 ms 332628 KB Output is correct
43 Correct 255 ms 332592 KB Output is correct
44 Correct 239 ms 332732 KB Output is correct
45 Correct 219 ms 330832 KB Output is correct
46 Correct 240 ms 334196 KB Output is correct
47 Correct 328 ms 338932 KB Output is correct
48 Correct 584 ms 360584 KB Output is correct
49 Correct 536 ms 360788 KB Output is correct
50 Correct 301 ms 328784 KB Output is correct
51 Correct 258 ms 328692 KB Output is correct
52 Correct 489 ms 354276 KB Output is correct
53 Correct 514 ms 354520 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 296748 KB Output is correct
2 Correct 52 ms 296788 KB Output is correct
3 Correct 113 ms 296532 KB Output is correct
4 Correct 43 ms 296320 KB Output is correct
5 Correct 48 ms 297108 KB Output is correct
6 Correct 96 ms 297040 KB Output is correct
7 Correct 45 ms 297016 KB Output is correct
8 Correct 96 ms 297056 KB Output is correct
9 Correct 112 ms 297044 KB Output is correct
10 Correct 41 ms 296416 KB Output is correct
11 Correct 114 ms 296788 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 296428 KB Output is correct
2 Correct 54 ms 296320 KB Output is correct
3 Correct 52 ms 296536 KB Output is correct
4 Correct 43 ms 296436 KB Output is correct
5 Correct 53 ms 296276 KB Output is correct
6 Correct 118 ms 296472 KB Output is correct
7 Correct 1276 ms 510204 KB Output is correct
8 Correct 2803 ms 749604 KB Output is correct
9 Correct 2887 ms 758208 KB Output is correct
10 Correct 2905 ms 752244 KB Output is correct
11 Correct 375 ms 408200 KB Output is correct
12 Correct 726 ms 499664 KB Output is correct
13 Correct 784 ms 512596 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 296468 KB Output is correct
2 Correct 70 ms 296532 KB Output is correct
3 Correct 56 ms 296532 KB Output is correct
4 Correct 61 ms 296432 KB Output is correct
5 Correct 51 ms 296460 KB Output is correct
6 Correct 54 ms 296404 KB Output is correct
7 Correct 47 ms 296460 KB Output is correct
8 Correct 42 ms 296516 KB Output is correct
9 Correct 45 ms 296432 KB Output is correct
10 Correct 42 ms 296536 KB Output is correct
11 Correct 45 ms 296532 KB Output is correct
12 Correct 49 ms 296580 KB Output is correct
13 Correct 44 ms 296276 KB Output is correct
14 Correct 75 ms 296484 KB Output is correct
15 Correct 74 ms 296500 KB Output is correct
16 Correct 47 ms 296440 KB Output is correct
17 Correct 80 ms 296952 KB Output is correct
18 Correct 77 ms 297044 KB Output is correct
19 Correct 111 ms 296928 KB Output is correct
20 Correct 60 ms 297044 KB Output is correct
21 Correct 68 ms 297196 KB Output is correct
22 Correct 50 ms 297172 KB Output is correct
23 Correct 120 ms 297252 KB Output is correct
24 Correct 80 ms 296808 KB Output is correct
25 Correct 67 ms 299196 KB Output is correct
26 Correct 66 ms 299208 KB Output is correct
27 Correct 86 ms 299264 KB Output is correct
28 Correct 120 ms 300172 KB Output is correct
29 Correct 106 ms 301396 KB Output is correct
30 Correct 96 ms 301492 KB Output is correct
31 Correct 102 ms 301140 KB Output is correct
32 Correct 105 ms 301004 KB Output is correct
33 Correct 243 ms 332884 KB Output is correct
34 Correct 191 ms 335660 KB Output is correct
35 Correct 203 ms 335880 KB Output is correct
36 Correct 207 ms 338732 KB Output is correct
37 Correct 254 ms 332628 KB Output is correct
38 Correct 255 ms 332592 KB Output is correct
39 Correct 239 ms 332732 KB Output is correct
40 Correct 219 ms 330832 KB Output is correct
41 Correct 240 ms 334196 KB Output is correct
42 Correct 328 ms 338932 KB Output is correct
43 Correct 584 ms 360584 KB Output is correct
44 Correct 536 ms 360788 KB Output is correct
45 Correct 301 ms 328784 KB Output is correct
46 Correct 258 ms 328692 KB Output is correct
47 Correct 489 ms 354276 KB Output is correct
48 Correct 514 ms 354520 KB Output is correct
49 Correct 44 ms 296748 KB Output is correct
50 Correct 52 ms 296788 KB Output is correct
51 Correct 113 ms 296532 KB Output is correct
52 Correct 43 ms 296320 KB Output is correct
53 Correct 48 ms 297108 KB Output is correct
54 Correct 96 ms 297040 KB Output is correct
55 Correct 45 ms 297016 KB Output is correct
56 Correct 96 ms 297056 KB Output is correct
57 Correct 112 ms 297044 KB Output is correct
58 Correct 41 ms 296416 KB Output is correct
59 Correct 114 ms 296788 KB Output is correct
60 Correct 118 ms 296472 KB Output is correct
61 Correct 1276 ms 510204 KB Output is correct
62 Correct 2803 ms 749604 KB Output is correct
63 Correct 2887 ms 758208 KB Output is correct
64 Correct 2905 ms 752244 KB Output is correct
65 Correct 375 ms 408200 KB Output is correct
66 Correct 726 ms 499664 KB Output is correct
67 Correct 784 ms 512596 KB Output is correct
68 Correct 53 ms 296428 KB Output is correct
69 Correct 54 ms 296320 KB Output is correct
70 Correct 52 ms 296536 KB Output is correct
71 Correct 43 ms 296436 KB Output is correct
72 Correct 53 ms 296276 KB Output is correct
73 Correct 2266 ms 706024 KB Output is correct
74 Correct 2118 ms 754440 KB Output is correct
75 Correct 2557 ms 750200 KB Output is correct
76 Correct 2188 ms 803760 KB Output is correct
77 Correct 2613 ms 700788 KB Output is correct
78 Correct 3694 ms 761600 KB Output is correct
79 Correct 3853 ms 789336 KB Output is correct
80 Runtime error 4139 ms 1048576 KB Execution killed with signal 9
81 Halted 0 ms 0 KB -