oj.uz

Submission #1047534

# Submission time Handle Problem Language Result Execution time Memory
1047534 2024-08-07T13:54:33 Z vjudge1 Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 843712 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
const int N = 2510;
int n,m;
vector<pair<short,short>> gdr[N];
vector<pair<short,short>> gdc[N];

struct Side {
	int r1, r2, c1, c2;
};
vector<pair<short,short>> hsides[N][N];
vector<pair<short,short>> vsides[N][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;
			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:134:8: warning: unused variable 'tmp' [-Wunused-variable]
  134 |    int tmp=0;
      |        ^~~
rect.cpp:98:10: warning: 'seg.Side::c1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |    seg.c1--;
      |    ~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296416 KB Output is correct
2 Correct 42 ms 296284 KB Output is correct
3 Correct 43 ms 296456 KB Output is correct
4 Correct 46 ms 296276 KB Output is correct
5 Correct 42 ms 296436 KB Output is correct
6 Correct 46 ms 296276 KB Output is correct
7 Correct 47 ms 296396 KB Output is correct
8 Correct 41 ms 296252 KB Output is correct
9 Correct 41 ms 296404 KB Output is correct
10 Correct 42 ms 296452 KB Output is correct
11 Correct 44 ms 296416 KB Output is correct
12 Correct 43 ms 296276 KB Output is correct
13 Correct 44 ms 296420 KB Output is correct
14 Correct 42 ms 296352 KB Output is correct
15 Correct 45 ms 296264 KB Output is correct
16 Correct 49 ms 296276 KB Output is correct
17 Correct 46 ms 296340 KB Output is correct
18 Correct 41 ms 296320 KB Output is correct
19 Correct 40 ms 296404 KB Output is correct
20 Correct 41 ms 296284 KB Output is correct
21 Correct 45 ms 296208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296416 KB Output is correct
2 Correct 42 ms 296284 KB Output is correct
3 Correct 43 ms 296456 KB Output is correct
4 Correct 46 ms 296276 KB Output is correct
5 Correct 42 ms 296436 KB Output is correct
6 Correct 46 ms 296276 KB Output is correct
7 Correct 47 ms 296396 KB Output is correct
8 Correct 41 ms 296252 KB Output is correct
9 Correct 41 ms 296404 KB Output is correct
10 Correct 42 ms 296452 KB Output is correct
11 Correct 44 ms 296416 KB Output is correct
12 Correct 43 ms 296276 KB Output is correct
13 Correct 44 ms 296420 KB Output is correct
14 Correct 42 ms 296352 KB Output is correct
15 Correct 45 ms 296264 KB Output is correct
16 Correct 49 ms 296276 KB Output is correct
17 Correct 46 ms 296340 KB Output is correct
18 Correct 41 ms 296320 KB Output is correct
19 Correct 40 ms 296404 KB Output is correct
20 Correct 41 ms 296284 KB Output is correct
21 Correct 45 ms 296208 KB Output is correct
22 Correct 43 ms 296748 KB Output is correct
23 Correct 44 ms 296740 KB Output is correct
24 Correct 45 ms 296696 KB Output is correct
25 Correct 44 ms 296788 KB Output is correct
26 Correct 46 ms 296936 KB Output is correct
27 Correct 50 ms 296928 KB Output is correct
28 Correct 50 ms 296796 KB Output is correct
29 Correct 46 ms 296496 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296416 KB Output is correct
2 Correct 42 ms 296284 KB Output is correct
3 Correct 43 ms 296456 KB Output is correct
4 Correct 46 ms 296276 KB Output is correct
5 Correct 42 ms 296436 KB Output is correct
6 Correct 46 ms 296276 KB Output is correct
7 Correct 47 ms 296396 KB Output is correct
8 Correct 41 ms 296252 KB Output is correct
9 Correct 41 ms 296404 KB Output is correct
10 Correct 42 ms 296452 KB Output is correct
11 Correct 44 ms 296416 KB Output is correct
12 Correct 43 ms 296276 KB Output is correct
13 Correct 44 ms 296420 KB Output is correct
14 Correct 42 ms 296352 KB Output is correct
15 Correct 45 ms 296264 KB Output is correct
16 Correct 49 ms 296276 KB Output is correct
17 Correct 43 ms 296748 KB Output is correct
18 Correct 44 ms 296740 KB Output is correct
19 Correct 45 ms 296696 KB Output is correct
20 Correct 44 ms 296788 KB Output is correct
21 Correct 46 ms 296936 KB Output is correct
22 Correct 50 ms 296928 KB Output is correct
23 Correct 50 ms 296796 KB Output is correct
24 Correct 46 ms 296496 KB Output is correct
25 Correct 46 ms 296340 KB Output is correct
26 Correct 41 ms 296320 KB Output is correct
27 Correct 40 ms 296404 KB Output is correct
28 Correct 41 ms 296284 KB Output is correct
29 Correct 45 ms 296208 KB Output is correct
30 Correct 51 ms 297812 KB Output is correct
31 Correct 51 ms 297740 KB Output is correct
32 Correct 50 ms 297876 KB Output is correct
33 Correct 62 ms 299228 KB Output is correct
34 Correct 72 ms 299744 KB Output is correct
35 Correct 72 ms 299824 KB Output is correct
36 Correct 79 ms 299544 KB Output is correct
37 Correct 78 ms 299604 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296416 KB Output is correct
2 Correct 42 ms 296284 KB Output is correct
3 Correct 43 ms 296456 KB Output is correct
4 Correct 46 ms 296276 KB Output is correct
5 Correct 42 ms 296436 KB Output is correct
6 Correct 46 ms 296276 KB Output is correct
7 Correct 47 ms 296396 KB Output is correct
8 Correct 41 ms 296252 KB Output is correct
9 Correct 41 ms 296404 KB Output is correct
10 Correct 42 ms 296452 KB Output is correct
11 Correct 44 ms 296416 KB Output is correct
12 Correct 43 ms 296276 KB Output is correct
13 Correct 44 ms 296420 KB Output is correct
14 Correct 42 ms 296352 KB Output is correct
15 Correct 45 ms 296264 KB Output is correct
16 Correct 49 ms 296276 KB Output is correct
17 Correct 43 ms 296748 KB Output is correct
18 Correct 44 ms 296740 KB Output is correct
19 Correct 45 ms 296696 KB Output is correct
20 Correct 44 ms 296788 KB Output is correct
21 Correct 46 ms 296936 KB Output is correct
22 Correct 50 ms 296928 KB Output is correct
23 Correct 50 ms 296796 KB Output is correct
24 Correct 46 ms 296496 KB Output is correct
25 Correct 51 ms 297812 KB Output is correct
26 Correct 51 ms 297740 KB Output is correct
27 Correct 50 ms 297876 KB Output is correct
28 Correct 62 ms 299228 KB Output is correct
29 Correct 72 ms 299744 KB Output is correct
30 Correct 72 ms 299824 KB Output is correct
31 Correct 79 ms 299544 KB Output is correct
32 Correct 78 ms 299604 KB Output is correct
33 Correct 46 ms 296340 KB Output is correct
34 Correct 41 ms 296320 KB Output is correct
35 Correct 40 ms 296404 KB Output is correct
36 Correct 41 ms 296284 KB Output is correct
37 Correct 45 ms 296208 KB Output is correct
38 Correct 182 ms 317444 KB Output is correct
39 Correct 162 ms 320900 KB Output is correct
40 Correct 189 ms 320944 KB Output is correct
41 Correct 163 ms 324180 KB Output is correct
42 Correct 151 ms 317012 KB Output is correct
43 Correct 150 ms 317240 KB Output is correct
44 Correct 153 ms 317012 KB Output is correct
45 Correct 146 ms 316420 KB Output is correct
46 Correct 228 ms 326224 KB Output is correct
47 Correct 282 ms 330060 KB Output is correct
48 Correct 452 ms 341072 KB Output is correct
49 Correct 453 ms 341328 KB Output is correct
50 Correct 239 ms 318836 KB Output is correct
51 Correct 241 ms 318808 KB Output is correct
52 Correct 441 ms 337540 KB Output is correct
53 Correct 454 ms 337624 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 296524 KB Output is correct
2 Correct 50 ms 296708 KB Output is correct
3 Correct 45 ms 296536 KB Output is correct
4 Correct 44 ms 296344 KB Output is correct
5 Correct 42 ms 296784 KB Output is correct
6 Correct 43 ms 296788 KB Output is correct
7 Correct 43 ms 296796 KB Output is correct
8 Correct 43 ms 296660 KB Output is correct
9 Correct 43 ms 296796 KB Output is correct
10 Correct 44 ms 296408 KB Output is correct
11 Correct 41 ms 296532 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296340 KB Output is correct
2 Correct 41 ms 296320 KB Output is correct
3 Correct 40 ms 296404 KB Output is correct
4 Correct 41 ms 296284 KB Output is correct
5 Correct 45 ms 296208 KB Output is correct
6 Correct 40 ms 296276 KB Output is correct
7 Correct 1279 ms 472816 KB Output is correct
8 Correct 2718 ms 668496 KB Output is correct
9 Correct 2754 ms 670212 KB Output is correct
10 Correct 2754 ms 670548 KB Output is correct
11 Correct 337 ms 371616 KB Output is correct
12 Correct 677 ms 430820 KB Output is correct
13 Correct 681 ms 439120 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 296416 KB Output is correct
2 Correct 42 ms 296284 KB Output is correct
3 Correct 43 ms 296456 KB Output is correct
4 Correct 46 ms 296276 KB Output is correct
5 Correct 42 ms 296436 KB Output is correct
6 Correct 46 ms 296276 KB Output is correct
7 Correct 47 ms 296396 KB Output is correct
8 Correct 41 ms 296252 KB Output is correct
9 Correct 41 ms 296404 KB Output is correct
10 Correct 42 ms 296452 KB Output is correct
11 Correct 44 ms 296416 KB Output is correct
12 Correct 43 ms 296276 KB Output is correct
13 Correct 44 ms 296420 KB Output is correct
14 Correct 42 ms 296352 KB Output is correct
15 Correct 45 ms 296264 KB Output is correct
16 Correct 49 ms 296276 KB Output is correct
17 Correct 43 ms 296748 KB Output is correct
18 Correct 44 ms 296740 KB Output is correct
19 Correct 45 ms 296696 KB Output is correct
20 Correct 44 ms 296788 KB Output is correct
21 Correct 46 ms 296936 KB Output is correct
22 Correct 50 ms 296928 KB Output is correct
23 Correct 50 ms 296796 KB Output is correct
24 Correct 46 ms 296496 KB Output is correct
25 Correct 51 ms 297812 KB Output is correct
26 Correct 51 ms 297740 KB Output is correct
27 Correct 50 ms 297876 KB Output is correct
28 Correct 62 ms 299228 KB Output is correct
29 Correct 72 ms 299744 KB Output is correct
30 Correct 72 ms 299824 KB Output is correct
31 Correct 79 ms 299544 KB Output is correct
32 Correct 78 ms 299604 KB Output is correct
33 Correct 182 ms 317444 KB Output is correct
34 Correct 162 ms 320900 KB Output is correct
35 Correct 189 ms 320944 KB Output is correct
36 Correct 163 ms 324180 KB Output is correct
37 Correct 151 ms 317012 KB Output is correct
38 Correct 150 ms 317240 KB Output is correct
39 Correct 153 ms 317012 KB Output is correct
40 Correct 146 ms 316420 KB Output is correct
41 Correct 228 ms 326224 KB Output is correct
42 Correct 282 ms 330060 KB Output is correct
43 Correct 452 ms 341072 KB Output is correct
44 Correct 453 ms 341328 KB Output is correct
45 Correct 239 ms 318836 KB Output is correct
46 Correct 241 ms 318808 KB Output is correct
47 Correct 441 ms 337540 KB Output is correct
48 Correct 454 ms 337624 KB Output is correct
49 Correct 41 ms 296524 KB Output is correct
50 Correct 50 ms 296708 KB Output is correct
51 Correct 45 ms 296536 KB Output is correct
52 Correct 44 ms 296344 KB Output is correct
53 Correct 42 ms 296784 KB Output is correct
54 Correct 43 ms 296788 KB Output is correct
55 Correct 43 ms 296796 KB Output is correct
56 Correct 43 ms 296660 KB Output is correct
57 Correct 43 ms 296796 KB Output is correct
58 Correct 44 ms 296408 KB Output is correct
59 Correct 41 ms 296532 KB Output is correct
60 Correct 40 ms 296276 KB Output is correct
61 Correct 1279 ms 472816 KB Output is correct
62 Correct 2718 ms 668496 KB Output is correct
63 Correct 2754 ms 670212 KB Output is correct
64 Correct 2754 ms 670548 KB Output is correct
65 Correct 337 ms 371616 KB Output is correct
66 Correct 677 ms 430820 KB Output is correct
67 Correct 681 ms 439120 KB Output is correct
68 Correct 46 ms 296340 KB Output is correct
69 Correct 41 ms 296320 KB Output is correct
70 Correct 40 ms 296404 KB Output is correct
71 Correct 41 ms 296284 KB Output is correct
72 Correct 45 ms 296208 KB Output is correct
73 Correct 1978 ms 538592 KB Output is correct
74 Correct 1860 ms 583888 KB Output is correct
75 Correct 2145 ms 584468 KB Output is correct
76 Correct 1916 ms 630672 KB Output is correct
77 Correct 2355 ms 538164 KB Output is correct
78 Correct 3375 ms 628460 KB Output is correct
79 Correct 3736 ms 646524 KB Output is correct
80 Execution timed out 5076 ms 843712 KB Time limit exceeded
81 Halted 0 ms 0 KB -