oj.uz

Submission #1054704

# Submission time Handle Problem Language Result Execution time Memory
1054704 2024-08-12T11:39:26 Z dozer Rectangles (IOI19_rect) C++14
72 / 100
 5000 ms 940128 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 t){
	int n = a.size(), m = a.front().size();
	if (t == 1) swap(n, m);
	for (int i = 1; i < n - 1; i++){
		
		set<int> s;
		vector<int> v(m);
		iota(v.begin(), v.end(), 0);
		sort(v.begin(), v.end(), [&](int x, int y){
			if (t == 0){
				if (a[i][x] == a[i][y]) return x < y;
				return a[i][x] > a[i][y];
			}
			else{
				if (a[x][i] == a[y][i]) return x < y;
				return a[x][i] > a[y][i];
			}
		});
		
		int it = 0;
		while(it < m){
			vector<int> tmp;
			int last = 0;
			if (t) last = a[v[it]][i];
			else last = a[i][v[it]];
			while(it < m){
				if (t == 0 && a[i][v[it]] != last) break;
				else if (t == 1 && a[v[it]][i] != last) break;
				tmp.pb(v[it]);
				it++;
			}
			
			for (int j = 0; j < tmp.size(); j++){
				int x = tmp[j];
				auto it2 = s.lower_bound(x);
				int prv = -1, nxt = m + 1;
				if (j > 0) prv = tmp[j - 1];
				if (j + 1 < tmp.size()) nxt = tmp[j + 1];
				
				if (it2 != s.begin() && !s.empty()){
					it2--;
					
					if (x - 1 > *it2) {
						if (t == 0) rng_h[i].pb({*it2 + 1, x - 1});
						else rng_v[i].pb({*it2 + 1, x - 1});
					}
				}
				it2 = s.lower_bound(x);
				if (it2 != s.end()){
					if (*it2 > x + 1 && *it2 < nxt) {
						
						if (t == 0) rng_h[i].pb({x + 1, *it2 - 1});
						else rng_v[i].pb({x + 1, *it2 - 1});
					}
				}
				
				s.insert(x);
			}
		}
		
	}
}
 
 
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, 0);
	compute(a, 1);
	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());
		/*
		cout<<i<<" : "<<endl;
		for (auto i : rng_h[i]) cout<<"("<<i.st<<sp<<i.nd<<") ";
		cout<<endl;*/
		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());
		/*
		cout<<i<<" : "<<endl;
		for (auto i : rng_v[i]) cout<<"("<<i.st<<sp<<i.nd<<") ";
		cout<<endl;*/
		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 'void compute(std::vector<std::vector<int> >&, int)':
rect.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int j = 0; j < tmp.size(); j++){
      |                    ~~^~~~~~~~~~~~
rect.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     if (j + 1 < tmp.size()) nxt = tmp[j + 1];
      |         ~~~~~~^~~~~~~~~~~~
rect.cpp:57:9: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
   57 |     int prv = -1, nxt = m + 1;
      |         ^~~
rect.cpp: In function 'int b_search(std::vector<int>&, int)':
rect.cpp:90:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   if (tmp >= v.size()) continue;
      |       ~~~~^~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:147: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]
  147 |    while(pos != rng_h[i].size() && rng_h[i][pos].st == j){
      |          ~~~~^~~~~~~~~~~~~~~~~~
rect.cpp:156: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]
  156 |    while(pos != rng_v[j].size() && rng_v[j][pos].st == i){
      |          ~~~~^~~~~~~~~~~~~~~~~~
rect.cpp:170: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]
  170 |     while(it < horr.size() && horr[it].st <= k.st){
      |           ~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 589776 KB Output is correct
2 Correct 152 ms 589804 KB Output is correct
3 Correct 164 ms 589904 KB Output is correct
4 Correct 195 ms 589912 KB Output is correct
5 Correct 149 ms 589904 KB Output is correct
6 Correct 156 ms 589908 KB Output is correct
7 Correct 176 ms 589908 KB Output is correct
8 Correct 162 ms 589964 KB Output is correct
9 Correct 160 ms 590004 KB Output is correct
10 Correct 160 ms 589800 KB Output is correct
11 Correct 161 ms 589968 KB Output is correct
12 Correct 165 ms 589948 KB Output is correct
13 Correct 191 ms 589860 KB Output is correct
14 Correct 151 ms 589864 KB Output is correct
15 Correct 167 ms 589976 KB Output is correct
16 Correct 159 ms 589908 KB Output is correct
17 Correct 170 ms 589964 KB Output is correct
18 Correct 153 ms 589908 KB Output is correct
19 Correct 160 ms 589948 KB Output is correct
20 Correct 158 ms 589860 KB Output is correct
21 Correct 198 ms 589848 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 589776 KB Output is correct
2 Correct 152 ms 589804 KB Output is correct
3 Correct 164 ms 589904 KB Output is correct
4 Correct 195 ms 589912 KB Output is correct
5 Correct 149 ms 589904 KB Output is correct
6 Correct 156 ms 589908 KB Output is correct
7 Correct 176 ms 589908 KB Output is correct
8 Correct 162 ms 589964 KB Output is correct
9 Correct 160 ms 590004 KB Output is correct
10 Correct 160 ms 589800 KB Output is correct
11 Correct 161 ms 589968 KB Output is correct
12 Correct 165 ms 589948 KB Output is correct
13 Correct 191 ms 589860 KB Output is correct
14 Correct 151 ms 589864 KB Output is correct
15 Correct 167 ms 589976 KB Output is correct
16 Correct 159 ms 589908 KB Output is correct
17 Correct 170 ms 589964 KB Output is correct
18 Correct 153 ms 589908 KB Output is correct
19 Correct 160 ms 589948 KB Output is correct
20 Correct 158 ms 589860 KB Output is correct
21 Correct 198 ms 589848 KB Output is correct
22 Correct 155 ms 590164 KB Output is correct
23 Correct 185 ms 590124 KB Output is correct
24 Correct 159 ms 590104 KB Output is correct
25 Correct 157 ms 589928 KB Output is correct
26 Correct 157 ms 590164 KB Output is correct
27 Correct 185 ms 590160 KB Output is correct
28 Correct 155 ms 590288 KB Output is correct
29 Correct 179 ms 589916 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 589776 KB Output is correct
2 Correct 152 ms 589804 KB Output is correct
3 Correct 164 ms 589904 KB Output is correct
4 Correct 195 ms 589912 KB Output is correct
5 Correct 149 ms 589904 KB Output is correct
6 Correct 156 ms 589908 KB Output is correct
7 Correct 176 ms 589908 KB Output is correct
8 Correct 162 ms 589964 KB Output is correct
9 Correct 160 ms 590004 KB Output is correct
10 Correct 160 ms 589800 KB Output is correct
11 Correct 161 ms 589968 KB Output is correct
12 Correct 165 ms 589948 KB Output is correct
13 Correct 191 ms 589860 KB Output is correct
14 Correct 151 ms 589864 KB Output is correct
15 Correct 167 ms 589976 KB Output is correct
16 Correct 159 ms 589908 KB Output is correct
17 Correct 155 ms 590164 KB Output is correct
18 Correct 185 ms 590124 KB Output is correct
19 Correct 159 ms 590104 KB Output is correct
20 Correct 157 ms 589928 KB Output is correct
21 Correct 157 ms 590164 KB Output is correct
22 Correct 185 ms 590160 KB Output is correct
23 Correct 155 ms 590288 KB Output is correct
24 Correct 179 ms 589916 KB Output is correct
25 Correct 170 ms 589964 KB Output is correct
26 Correct 153 ms 589908 KB Output is correct
27 Correct 160 ms 589948 KB Output is correct
28 Correct 158 ms 589860 KB Output is correct
29 Correct 198 ms 589848 KB Output is correct
30 Correct 222 ms 591700 KB Output is correct
31 Correct 179 ms 591700 KB Output is correct
32 Correct 171 ms 591616 KB Output is correct
33 Correct 181 ms 590784 KB Output is correct
34 Correct 199 ms 591696 KB Output is correct
35 Correct 180 ms 592024 KB Output is correct
36 Correct 177 ms 591664 KB Output is correct
37 Correct 176 ms 591712 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 589776 KB Output is correct
2 Correct 152 ms 589804 KB Output is correct
3 Correct 164 ms 589904 KB Output is correct
4 Correct 195 ms 589912 KB Output is correct
5 Correct 149 ms 589904 KB Output is correct
6 Correct 156 ms 589908 KB Output is correct
7 Correct 176 ms 589908 KB Output is correct
8 Correct 162 ms 589964 KB Output is correct
9 Correct 160 ms 590004 KB Output is correct
10 Correct 160 ms 589800 KB Output is correct
11 Correct 161 ms 589968 KB Output is correct
12 Correct 165 ms 589948 KB Output is correct
13 Correct 191 ms 589860 KB Output is correct
14 Correct 151 ms 589864 KB Output is correct
15 Correct 167 ms 589976 KB Output is correct
16 Correct 159 ms 589908 KB Output is correct
17 Correct 155 ms 590164 KB Output is correct
18 Correct 185 ms 590124 KB Output is correct
19 Correct 159 ms 590104 KB Output is correct
20 Correct 157 ms 589928 KB Output is correct
21 Correct 157 ms 590164 KB Output is correct
22 Correct 185 ms 590160 KB Output is correct
23 Correct 155 ms 590288 KB Output is correct
24 Correct 179 ms 589916 KB Output is correct
25 Correct 222 ms 591700 KB Output is correct
26 Correct 179 ms 591700 KB Output is correct
27 Correct 171 ms 591616 KB Output is correct
28 Correct 181 ms 590784 KB Output is correct
29 Correct 199 ms 591696 KB Output is correct
30 Correct 180 ms 592024 KB Output is correct
31 Correct 177 ms 591664 KB Output is correct
32 Correct 176 ms 591712 KB Output is correct
33 Correct 170 ms 589964 KB Output is correct
34 Correct 153 ms 589908 KB Output is correct
35 Correct 160 ms 589948 KB Output is correct
36 Correct 158 ms 589860 KB Output is correct
37 Correct 198 ms 589848 KB Output is correct
38 Correct 381 ms 616924 KB Output is correct
39 Correct 362 ms 616940 KB Output is correct
40 Correct 354 ms 616788 KB Output is correct
41 Correct 355 ms 616784 KB Output is correct
42 Correct 431 ms 613116 KB Output is correct
43 Correct 448 ms 613200 KB Output is correct
44 Correct 435 ms 613460 KB Output is correct
45 Correct 411 ms 612432 KB Output is correct
46 Correct 364 ms 598864 KB Output is correct
47 Correct 411 ms 602452 KB Output is correct
48 Correct 577 ms 612944 KB Output is correct
49 Correct 568 ms 614176 KB Output is correct
50 Correct 348 ms 602020 KB Output is correct
51 Correct 347 ms 602300 KB Output is correct
52 Correct 550 ms 612400 KB Output is correct
53 Correct 602 ms 612876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 590164 KB Output is correct
2 Correct 153 ms 590164 KB Output is correct
3 Correct 158 ms 589964 KB Output is correct
4 Correct 155 ms 589828 KB Output is correct
5 Correct 162 ms 590160 KB Output is correct
6 Correct 152 ms 590164 KB Output is correct
7 Correct 154 ms 590164 KB Output is correct
8 Correct 150 ms 590296 KB Output is correct
9 Correct 149 ms 590164 KB Output is correct
10 Correct 149 ms 589904 KB Output is correct
11 Correct 149 ms 589908 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 589964 KB Output is correct
2 Correct 153 ms 589908 KB Output is correct
3 Correct 160 ms 589948 KB Output is correct
4 Correct 158 ms 589860 KB Output is correct
5 Correct 198 ms 589848 KB Output is correct
6 Correct 153 ms 589908 KB Output is correct
7 Correct 1519 ms 645276 KB Output is correct
8 Correct 3216 ms 706416 KB Output is correct
9 Correct 3252 ms 706580 KB Output is correct
10 Correct 3239 ms 706800 KB Output is correct
11 Correct 832 ms 618068 KB Output is correct
12 Correct 1509 ms 642644 KB Output is correct
13 Correct 1632 ms 645888 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 589776 KB Output is correct
2 Correct 152 ms 589804 KB Output is correct
3 Correct 164 ms 589904 KB Output is correct
4 Correct 195 ms 589912 KB Output is correct
5 Correct 149 ms 589904 KB Output is correct
6 Correct 156 ms 589908 KB Output is correct
7 Correct 176 ms 589908 KB Output is correct
8 Correct 162 ms 589964 KB Output is correct
9 Correct 160 ms 590004 KB Output is correct
10 Correct 160 ms 589800 KB Output is correct
11 Correct 161 ms 589968 KB Output is correct
12 Correct 165 ms 589948 KB Output is correct
13 Correct 191 ms 589860 KB Output is correct
14 Correct 151 ms 589864 KB Output is correct
15 Correct 167 ms 589976 KB Output is correct
16 Correct 159 ms 589908 KB Output is correct
17 Correct 155 ms 590164 KB Output is correct
18 Correct 185 ms 590124 KB Output is correct
19 Correct 159 ms 590104 KB Output is correct
20 Correct 157 ms 589928 KB Output is correct
21 Correct 157 ms 590164 KB Output is correct
22 Correct 185 ms 590160 KB Output is correct
23 Correct 155 ms 590288 KB Output is correct
24 Correct 179 ms 589916 KB Output is correct
25 Correct 222 ms 591700 KB Output is correct
26 Correct 179 ms 591700 KB Output is correct
27 Correct 171 ms 591616 KB Output is correct
28 Correct 181 ms 590784 KB Output is correct
29 Correct 199 ms 591696 KB Output is correct
30 Correct 180 ms 592024 KB Output is correct
31 Correct 177 ms 591664 KB Output is correct
32 Correct 176 ms 591712 KB Output is correct
33 Correct 381 ms 616924 KB Output is correct
34 Correct 362 ms 616940 KB Output is correct
35 Correct 354 ms 616788 KB Output is correct
36 Correct 355 ms 616784 KB Output is correct
37 Correct 431 ms 613116 KB Output is correct
38 Correct 448 ms 613200 KB Output is correct
39 Correct 435 ms 613460 KB Output is correct
40 Correct 411 ms 612432 KB Output is correct
41 Correct 364 ms 598864 KB Output is correct
42 Correct 411 ms 602452 KB Output is correct
43 Correct 577 ms 612944 KB Output is correct
44 Correct 568 ms 614176 KB Output is correct
45 Correct 348 ms 602020 KB Output is correct
46 Correct 347 ms 602300 KB Output is correct
47 Correct 550 ms 612400 KB Output is correct
48 Correct 602 ms 612876 KB Output is correct
49 Correct 151 ms 590164 KB Output is correct
50 Correct 153 ms 590164 KB Output is correct
51 Correct 158 ms 589964 KB Output is correct
52 Correct 155 ms 589828 KB Output is correct
53 Correct 162 ms 590160 KB Output is correct
54 Correct 152 ms 590164 KB Output is correct
55 Correct 154 ms 590164 KB Output is correct
56 Correct 150 ms 590296 KB Output is correct
57 Correct 149 ms 590164 KB Output is correct
58 Correct 149 ms 589904 KB Output is correct
59 Correct 149 ms 589908 KB Output is correct
60 Correct 153 ms 589908 KB Output is correct
61 Correct 1519 ms 645276 KB Output is correct
62 Correct 3216 ms 706416 KB Output is correct
63 Correct 3252 ms 706580 KB Output is correct
64 Correct 3239 ms 706800 KB Output is correct
65 Correct 832 ms 618068 KB Output is correct
66 Correct 1509 ms 642644 KB Output is correct
67 Correct 1632 ms 645888 KB Output is correct
68 Correct 170 ms 589964 KB Output is correct
69 Correct 153 ms 589908 KB Output is correct
70 Correct 160 ms 589948 KB Output is correct
71 Correct 158 ms 589860 KB Output is correct
72 Correct 198 ms 589848 KB Output is correct
73 Correct 3445 ms 928760 KB Output is correct
74 Correct 3391 ms 928628 KB Output is correct
75 Correct 3394 ms 930216 KB Output is correct
76 Correct 3200 ms 940128 KB Output is correct
77 Correct 4751 ms 855532 KB Output is correct
78 Correct 3725 ms 745772 KB Output is correct
79 Correct 3922 ms 762384 KB Output is correct
80 Execution timed out 5022 ms 839932 KB Time limit exceeded
81 Halted 0 ms 0 KB -