oj.uz

Submission #1054732

# Submission time Handle Problem Language Result Execution time Memory
1054732 2024-08-12T11:49:28 Z dozer Rectangles (IOI19_rect) C++14
100 / 100
 3377 ms 913872 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 2505
#define LOGN 12
 
vector<pii> rng_h[MAXN], rng_v[MAXN];
vector<int> hor[MAXN][MAXN], ver[MAXN][MAXN];
vector<int> nxt_hor[MAXN][MAXN], nxt_ver[MAXN][MAXN];

void compute(vector<vector<int>> &a){
		int n = a.size(), m = a.front().size();
	for (int i = 1; i < n - 1; i++){
		vector<int> nxt(m), prv(m);
		nxt[m - 1] = m;
		for (int j = m - 2; j >= 0; j--){
			nxt[j] = j + 1;
			while(nxt[j] < m && a[i][nxt[j]] <= a[i][j]) nxt[j] = nxt[nxt[j]];
		}
		prv[0] = -1;
		for (int j = 1; j < m; j++){
			prv[j] = j - 1;
			while(prv[j] != -1 && a[i][prv[j]] <= a[i][j]) prv[j] = prv[prv[j]];
		}
 
		for (int j = 1; j < m - 1; j++)
			if (prv[j] != -1 && nxt[j] != m && prv[j] < nxt[j] + 1) rng_h[i].pb({prv[j] + 1, nxt[j] - 1});
		
	}
 
	swap(n, m);
	for (int i = 1; i < n - 1; i++){
		vector<int> nxt(m), prv(m);
		nxt[m - 1] = m;
		for (int j = m - 2; j >= 0; j--){
			nxt[j] = j + 1;
			while(nxt[j] < m && a[nxt[j]][i] <= a[j][i]) nxt[j] = nxt[nxt[j]];
		}
		prv[0] = -1;
		for (int j = 1; j < m; j++){
			prv[j] = j - 1;
			while(prv[j] != -1 && a[prv[j]][i] <= a[j][i]) prv[j] = prv[prv[j]];
		}
 
		for (int j = 1; j < m - 1; j++)
			if (prv[j] != -1 && nxt[j] != m && prv[j] < nxt[j] + 1) rng_v[i].pb({prv[j] + 1, nxt[j] - 1});
	}
}
 
 
int b_search(vector<int> &v, int pos){
	int ans = pos;
	for (int i = LOGN; i >= 0; i--){
		int tmp = ans + (1<<i);
		if (tmp >= v.size()) continue;
		if (v[tmp] - v[pos] == tmp - pos) ans = tmp;
	}
	return ans;
}
 
int tree[MAXN];

void update(int x, int val, int n){
	while(x <= n){
		tree[x] += val;
		x+=x&-x;
	}
}


int query(int x){
	int ans = 0;
	while(x > 0) {
		ans += tree[x];
		x-=x&-x;
	}
	return ans;
}

long long count_rectangles(vector<vector<int>> a){
	compute(a);
	int n = a.size(), m = a.front().size();
	for (int i = 1; i < n - 1; i++){
		sort(rng_h[i].begin(), rng_h[i].end());
		vector<pii> tmp;
		for (auto i : rng_h[i]) if(tmp.empty() || tmp.back() != i) tmp.pb(i);
		rng_h[i] = tmp;

		for (auto j : rng_h[i]){
			hor[j.st][j.nd].pb(i);
		}
	}
 
	for (int i = 1; i < m - 1; i++){
		sort(rng_v[i].begin(), rng_v[i].end());
		vector<pii> tmp;
		for (auto i : rng_v[i]) if(tmp.empty() || tmp.back() != i) tmp.pb(i);
		rng_v[i] = tmp;
		for (auto j : rng_v[i]){
			ver[j.st][j.nd].pb(i);
		}
	}

	long long ans = 0;
	
	for (int i = 1; i < n - 1; i++){
		for (int j = 1; j < m - 1; j++){
			vector<pii> horr, verr;
			int pos = lower_bound(rng_h[i].begin(), rng_h[i].end(), make_pair(j, 0)) - rng_h[i].begin(); 	
			while(pos != rng_h[i].size() && rng_h[i][pos].st == j){
				int l = j, r = rng_h[i][pos].nd;
				pos++;
				int curr = lower_bound(hor[l][r].begin(), hor[l][r].end(), i) - hor[l][r].begin();
				int to = hor[l][r][b_search(hor[l][r], curr)];
				horr.pb({r, to});
			}

			pos = lower_bound(rng_v[j].begin(), rng_v[j].end(), make_pair(i, 0)) - rng_v[j].begin();
			while(pos != rng_v[j].size() && rng_v[j][pos].st == i){
				int l = i, r = rng_v[j][pos].nd;
				pos++;
				int curr = lower_bound(ver[l][r].begin(), ver[l][r].end(), j) - ver[l][r].begin();
				int to = ver[l][r][b_search(ver[l][r], curr)];
				verr.pb({to, r});
			}
			sort(horr.begin(), horr.end());
			sort(verr.begin(), verr.end());

			int it = 0;
			vector<int> del;
			for (auto k : verr){
				
				while(it < horr.size() && horr[it].st <= k.st){
					del.pb(horr[it].nd);
					update(horr[it].nd, 1, n);
					it++;
				}
				ans += query(n) - query(k.nd - 1);
			}

			for (auto i : del){
				update(i, -1, n);
			}
		}
	}
	return ans;
 
	return 0;
}
 
 /*

int main() {
	fileio();
	int n, m;
	cin>>n>>m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++) {
			cin>>a[i][j];
		}
	}
	long long result = count_rectangles(a);
 
	printf("%lld\n", result);
	return 0;
}*/

Compilation message

rect.cpp: In function 'int b_search(std::vector<int>&, int)':
rect.cpp:66:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if (tmp >= v.size()) continue;
      |       ~~~~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:121:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    while(pos != rng_h[i].size() && rng_h[i][pos].st == j){
      |          ~~~~^~~~~~~~~~~~~~~~~~
rect.cpp:130:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |    while(pos != rng_v[j].size() && rng_v[j][pos].st == i){
      |          ~~~~^~~~~~~~~~~~~~~~~~
rect.cpp:144:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     while(it < horr.size() && horr[it].st <= k.st){
      |           ~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 589836 KB Output is correct
2 Correct 151 ms 589904 KB Output is correct
3 Correct 154 ms 589760 KB Output is correct
4 Correct 158 ms 590088 KB Output is correct
5 Correct 153 ms 589904 KB Output is correct
6 Correct 153 ms 589904 KB Output is correct
7 Correct 150 ms 589908 KB Output is correct
8 Correct 153 ms 589836 KB Output is correct
9 Correct 156 ms 589816 KB Output is correct
10 Correct 151 ms 589908 KB Output is correct
11 Correct 153 ms 589960 KB Output is correct
12 Correct 151 ms 589908 KB Output is correct
13 Correct 151 ms 589908 KB Output is correct
14 Correct 163 ms 589908 KB Output is correct
15 Correct 163 ms 589916 KB Output is correct
16 Correct 149 ms 589904 KB Output is correct
17 Correct 156 ms 589724 KB Output is correct
18 Correct 157 ms 589796 KB Output is correct
19 Correct 150 ms 589788 KB Output is correct
20 Correct 150 ms 589904 KB Output is correct
21 Correct 153 ms 589908 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 589836 KB Output is correct
2 Correct 151 ms 589904 KB Output is correct
3 Correct 154 ms 589760 KB Output is correct
4 Correct 158 ms 590088 KB Output is correct
5 Correct 153 ms 589904 KB Output is correct
6 Correct 153 ms 589904 KB Output is correct
7 Correct 150 ms 589908 KB Output is correct
8 Correct 153 ms 589836 KB Output is correct
9 Correct 156 ms 589816 KB Output is correct
10 Correct 151 ms 589908 KB Output is correct
11 Correct 153 ms 589960 KB Output is correct
12 Correct 151 ms 589908 KB Output is correct
13 Correct 151 ms 589908 KB Output is correct
14 Correct 163 ms 589908 KB Output is correct
15 Correct 163 ms 589916 KB Output is correct
16 Correct 149 ms 589904 KB Output is correct
17 Correct 156 ms 589724 KB Output is correct
18 Correct 157 ms 589796 KB Output is correct
19 Correct 150 ms 589788 KB Output is correct
20 Correct 150 ms 589904 KB Output is correct
21 Correct 153 ms 589908 KB Output is correct
22 Correct 158 ms 590288 KB Output is correct
23 Correct 154 ms 590160 KB Output is correct
24 Correct 154 ms 590164 KB Output is correct
25 Correct 158 ms 590036 KB Output is correct
26 Correct 151 ms 590164 KB Output is correct
27 Correct 152 ms 590164 KB Output is correct
28 Correct 153 ms 590164 KB Output is correct
29 Correct 154 ms 590120 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 589836 KB Output is correct
2 Correct 151 ms 589904 KB Output is correct
3 Correct 154 ms 589760 KB Output is correct
4 Correct 158 ms 590088 KB Output is correct
5 Correct 153 ms 589904 KB Output is correct
6 Correct 153 ms 589904 KB Output is correct
7 Correct 150 ms 589908 KB Output is correct
8 Correct 153 ms 589836 KB Output is correct
9 Correct 156 ms 589816 KB Output is correct
10 Correct 151 ms 589908 KB Output is correct
11 Correct 153 ms 589960 KB Output is correct
12 Correct 151 ms 589908 KB Output is correct
13 Correct 151 ms 589908 KB Output is correct
14 Correct 163 ms 589908 KB Output is correct
15 Correct 163 ms 589916 KB Output is correct
16 Correct 149 ms 589904 KB Output is correct
17 Correct 158 ms 590288 KB Output is correct
18 Correct 154 ms 590160 KB Output is correct
19 Correct 154 ms 590164 KB Output is correct
20 Correct 158 ms 590036 KB Output is correct
21 Correct 151 ms 590164 KB Output is correct
22 Correct 152 ms 590164 KB Output is correct
23 Correct 153 ms 590164 KB Output is correct
24 Correct 154 ms 590120 KB Output is correct
25 Correct 156 ms 589724 KB Output is correct
26 Correct 157 ms 589796 KB Output is correct
27 Correct 150 ms 589788 KB Output is correct
28 Correct 150 ms 589904 KB Output is correct
29 Correct 153 ms 589908 KB Output is correct
30 Correct 165 ms 591556 KB Output is correct
31 Correct 164 ms 591696 KB Output is correct
32 Correct 167 ms 591696 KB Output is correct
33 Correct 162 ms 591224 KB Output is correct
34 Correct 171 ms 591700 KB Output is correct
35 Correct 175 ms 591956 KB Output is correct
36 Correct 164 ms 591716 KB Output is correct
37 Correct 169 ms 591820 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 589836 KB Output is correct
2 Correct 151 ms 589904 KB Output is correct
3 Correct 154 ms 589760 KB Output is correct
4 Correct 158 ms 590088 KB Output is correct
5 Correct 153 ms 589904 KB Output is correct
6 Correct 153 ms 589904 KB Output is correct
7 Correct 150 ms 589908 KB Output is correct
8 Correct 153 ms 589836 KB Output is correct
9 Correct 156 ms 589816 KB Output is correct
10 Correct 151 ms 589908 KB Output is correct
11 Correct 153 ms 589960 KB Output is correct
12 Correct 151 ms 589908 KB Output is correct
13 Correct 151 ms 589908 KB Output is correct
14 Correct 163 ms 589908 KB Output is correct
15 Correct 163 ms 589916 KB Output is correct
16 Correct 149 ms 589904 KB Output is correct
17 Correct 158 ms 590288 KB Output is correct
18 Correct 154 ms 590160 KB Output is correct
19 Correct 154 ms 590164 KB Output is correct
20 Correct 158 ms 590036 KB Output is correct
21 Correct 151 ms 590164 KB Output is correct
22 Correct 152 ms 590164 KB Output is correct
23 Correct 153 ms 590164 KB Output is correct
24 Correct 154 ms 590120 KB Output is correct
25 Correct 165 ms 591556 KB Output is correct
26 Correct 164 ms 591696 KB Output is correct
27 Correct 167 ms 591696 KB Output is correct
28 Correct 162 ms 591224 KB Output is correct
29 Correct 171 ms 591700 KB Output is correct
30 Correct 175 ms 591956 KB Output is correct
31 Correct 164 ms 591716 KB Output is correct
32 Correct 169 ms 591820 KB Output is correct
33 Correct 156 ms 589724 KB Output is correct
34 Correct 157 ms 589796 KB Output is correct
35 Correct 150 ms 589788 KB Output is correct
36 Correct 150 ms 589904 KB Output is correct
37 Correct 153 ms 589908 KB Output is correct
38 Correct 236 ms 616024 KB Output is correct
39 Correct 229 ms 616112 KB Output is correct
40 Correct 224 ms 616016 KB Output is correct
41 Correct 220 ms 616416 KB Output is correct
42 Correct 277 ms 611920 KB Output is correct
43 Correct 277 ms 612052 KB Output is correct
44 Correct 279 ms 612428 KB Output is correct
45 Correct 270 ms 611388 KB Output is correct
46 Correct 234 ms 601500 KB Output is correct
47 Correct 254 ms 602448 KB Output is correct
48 Correct 347 ms 612280 KB Output is correct
49 Correct 357 ms 613072 KB Output is correct
50 Correct 254 ms 601940 KB Output is correct
51 Correct 260 ms 601936 KB Output is correct
52 Correct 366 ms 611664 KB Output is correct
53 Correct 348 ms 611920 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 590140 KB Output is correct
2 Correct 149 ms 589956 KB Output is correct
3 Correct 149 ms 590016 KB Output is correct
4 Correct 149 ms 589840 KB Output is correct
5 Correct 147 ms 590164 KB Output is correct
6 Correct 150 ms 589964 KB Output is correct
7 Correct 149 ms 590160 KB Output is correct
8 Correct 152 ms 590032 KB Output is correct
9 Correct 185 ms 590156 KB Output is correct
10 Correct 157 ms 589904 KB Output is correct
11 Correct 150 ms 589904 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 589724 KB Output is correct
2 Correct 157 ms 589796 KB Output is correct
3 Correct 150 ms 589788 KB Output is correct
4 Correct 150 ms 589904 KB Output is correct
5 Correct 153 ms 589908 KB Output is correct
6 Correct 150 ms 589908 KB Output is correct
7 Correct 678 ms 657896 KB Output is correct
8 Correct 1325 ms 729172 KB Output is correct
9 Correct 1404 ms 729168 KB Output is correct
10 Correct 1366 ms 729648 KB Output is correct
11 Correct 234 ms 614096 KB Output is correct
12 Correct 302 ms 635964 KB Output is correct
13 Correct 313 ms 639100 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 589836 KB Output is correct
2 Correct 151 ms 589904 KB Output is correct
3 Correct 154 ms 589760 KB Output is correct
4 Correct 158 ms 590088 KB Output is correct
5 Correct 153 ms 589904 KB Output is correct
6 Correct 153 ms 589904 KB Output is correct
7 Correct 150 ms 589908 KB Output is correct
8 Correct 153 ms 589836 KB Output is correct
9 Correct 156 ms 589816 KB Output is correct
10 Correct 151 ms 589908 KB Output is correct
11 Correct 153 ms 589960 KB Output is correct
12 Correct 151 ms 589908 KB Output is correct
13 Correct 151 ms 589908 KB Output is correct
14 Correct 163 ms 589908 KB Output is correct
15 Correct 163 ms 589916 KB Output is correct
16 Correct 149 ms 589904 KB Output is correct
17 Correct 158 ms 590288 KB Output is correct
18 Correct 154 ms 590160 KB Output is correct
19 Correct 154 ms 590164 KB Output is correct
20 Correct 158 ms 590036 KB Output is correct
21 Correct 151 ms 590164 KB Output is correct
22 Correct 152 ms 590164 KB Output is correct
23 Correct 153 ms 590164 KB Output is correct
24 Correct 154 ms 590120 KB Output is correct
25 Correct 165 ms 591556 KB Output is correct
26 Correct 164 ms 591696 KB Output is correct
27 Correct 167 ms 591696 KB Output is correct
28 Correct 162 ms 591224 KB Output is correct
29 Correct 171 ms 591700 KB Output is correct
30 Correct 175 ms 591956 KB Output is correct
31 Correct 164 ms 591716 KB Output is correct
32 Correct 169 ms 591820 KB Output is correct
33 Correct 236 ms 616024 KB Output is correct
34 Correct 229 ms 616112 KB Output is correct
35 Correct 224 ms 616016 KB Output is correct
36 Correct 220 ms 616416 KB Output is correct
37 Correct 277 ms 611920 KB Output is correct
38 Correct 277 ms 612052 KB Output is correct
39 Correct 279 ms 612428 KB Output is correct
40 Correct 270 ms 611388 KB Output is correct
41 Correct 234 ms 601500 KB Output is correct
42 Correct 254 ms 602448 KB Output is correct
43 Correct 347 ms 612280 KB Output is correct
44 Correct 357 ms 613072 KB Output is correct
45 Correct 254 ms 601940 KB Output is correct
46 Correct 260 ms 601936 KB Output is correct
47 Correct 366 ms 611664 KB Output is correct
48 Correct 348 ms 611920 KB Output is correct
49 Correct 150 ms 590140 KB Output is correct
50 Correct 149 ms 589956 KB Output is correct
51 Correct 149 ms 590016 KB Output is correct
52 Correct 149 ms 589840 KB Output is correct
53 Correct 147 ms 590164 KB Output is correct
54 Correct 150 ms 589964 KB Output is correct
55 Correct 149 ms 590160 KB Output is correct
56 Correct 152 ms 590032 KB Output is correct
57 Correct 185 ms 590156 KB Output is correct
58 Correct 157 ms 589904 KB Output is correct
59 Correct 150 ms 589904 KB Output is correct
60 Correct 150 ms 589908 KB Output is correct
61 Correct 678 ms 657896 KB Output is correct
62 Correct 1325 ms 729172 KB Output is correct
63 Correct 1404 ms 729168 KB Output is correct
64 Correct 1366 ms 729648 KB Output is correct
65 Correct 234 ms 614096 KB Output is correct
66 Correct 302 ms 635964 KB Output is correct
67 Correct 313 ms 639100 KB Output is correct
68 Correct 156 ms 589724 KB Output is correct
69 Correct 157 ms 589796 KB Output is correct
70 Correct 150 ms 589788 KB Output is correct
71 Correct 150 ms 589904 KB Output is correct
72 Correct 153 ms 589908 KB Output is correct
73 Correct 1791 ms 913872 KB Output is correct
74 Correct 1501 ms 903508 KB Output is correct
75 Correct 1354 ms 901784 KB Output is correct
76 Correct 1111 ms 896080 KB Output is correct
77 Correct 2317 ms 843960 KB Output is correct
78 Correct 1962 ms 742976 KB Output is correct
79 Correct 2094 ms 757144 KB Output is correct
80 Correct 3243 ms 835788 KB Output is correct
81 Correct 1981 ms 769672 KB Output is correct
82 Correct 2705 ms 818728 KB Output is correct
83 Correct 3283 ms 880308 KB Output is correct
84 Correct 1886 ms 754400 KB Output is correct
85 Correct 3377 ms 871328 KB Output is correct
86 Correct 3152 ms 863664 KB Output is correct
87 Correct 1402 ms 765444 KB Output is correct
88 Correct 2223 ms 879444 KB Output is correct
89 Correct 2396 ms 879516 KB Output is correct
90 Correct 2370 ms 879712 KB Output is correct