oj.uz

Submission #144774

# Submission time Handle Problem Language Result Execution time Memory
144774 2019-08-17T16:39:11 Z nvmdava Rectangles (IOI19_rect) C++17
100 / 100
 4969 ms 930548 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define N 2501
 
map<int, int> cnt[N][N][2];
int arr[N][N], bit[N], temp[N], p[N], lc[N], rc[N], n, m;
vector<int> v;
vector<int> t;
inline void buildtree(int sz){
 
	v = {0};
	for(int i = 1; i <= sz; i++){
		t.clear();
		while(temp[v.back()] < temp[i]){
			t.push_back(v.back());
			v.pop_back();
		}
		v.push_back(i);
		for(int j = t.size() - 1; j > 0; j--){
			p[t[j - 1]] = t[j];
		}
		if(!t.empty()) p[t.back()] = i;
	}
	for(int i = v.size() - 1; i > 0; i--)
		p[v[i]] = v[i - 1];
	for(int i = 1; i <= sz; i++){
		if(p[i] > i){
			lc[p[i]] = i;
		} else {
			rc[p[i]] = i;
		}
	}
 
}
 
void travtree(int i1, int i2, int v, int l, int r){
	if(l != 0 && r != (i1 == 1 ? n + 1 : m + 1) && r - l > 1 && temp[l] != temp[v] && temp[r] != temp[v]){
		if(i1 == 0)
			cnt[i2][r - 1][0][r - l - 1]++;
		else 
			cnt[r - 1][i2][1][r - l - 1]++;
	}
	if(lc[v] != 0)
		travtree(i1, i2, lc[v], l, v);
	if(rc[v] != 0)
		travtree(i1, i2, rc[v], v, r);
}
 
inline void build(){
	for(int j = 1; j <= m; j++){
		memset(lc, 0, sizeof lc);
		memset(rc, 0, sizeof rc);
 
		for(int i = 0; i <= n; i++)
			temp[i] = arr[i][j];
		
		buildtree(n);
		travtree(1, j, 0, 0, n + 1);
	}
}
 
inline void update(int x, int v){
	for(int i = x; i < N; i += i & -i)
		bit[i] += v;
}
 
inline int query(int x){
	int res = 0;
	for(int i = x; i > 0; i -= i & -i)
		res += bit[i];
	return res;
}
vector<pair<int, int> > sad;
int i1;
bool sw;
long long count_rectangles(vector<vector<int> > a){
	n = a.size();
	m = a[0].size();
	
	for(int i = 0; i < N; i++){
		arr[0][i] = 0x3f3f3f3f;
		arr[i][0] = 0x3f3f3f3f;
	}
 
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			arr[i + 1][j + 1] = a[i][j];
	a.clear();
	build();
	int res = 0;
	for(int i = 1; i <= n; i++){
		memset(lc, 0, sizeof lc);
		memset(rc, 0, sizeof rc);
		for(int j = 0; j <= m; j++)
			temp[j] = arr[i][j];
		buildtree(m);
		travtree(0, i, 0, 0, m + 1);
		for(int j = 1; j <= m; j++){
			sw = 0;
			sad.clear();
			for(auto& x : cnt[i][j][0]){
				auto it = cnt[i - 1][j][0].find(x.ff);
				if(it != cnt[i - 1][j][0].end())
					x.ss = 1 + it -> ss;
			}
			for(auto& x : cnt[i][j][1]){
				auto it = cnt[i][j - 1][1].find(x.ff);
				if(it != cnt[i][j - 1][1].end())
					x.ss = 1 + it -> ss;
			}
			if(cnt[i][j][0].size() > cnt[i][j][1].size()) sw = 1;
 
			for(auto& x : cnt[i][j][sw]){
				sad.push_back({x.ss, x.ff});
				update(x.ff, 1);
			}
 
			sort(sad.rbegin(), sad.rend());
			i1 = sad.size() - 1;
			sw ^= 1;
			for(auto& x : cnt[i][j][sw]){
				while(i1 >= 0 && sad[i1].ff < x.ff)
					update(sad[i1--].ss, -1);
 
				res += query(x.ss);
			}
			while(i1 >= 0)
				update(sad[i1--].ss, -1);
			cnt[i - 1][j][0].clear();
			cnt[i - 1][j][1].clear();
		}
	}
	return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 597996 KB Output is correct
2 Correct 546 ms 598136 KB Output is correct
3 Correct 543 ms 598008 KB Output is correct
4 Correct 553 ms 598008 KB Output is correct
5 Correct 538 ms 598008 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 540 ms 597920 KB Output is correct
8 Correct 542 ms 598092 KB Output is correct
9 Correct 541 ms 597996 KB Output is correct
10 Correct 542 ms 598076 KB Output is correct
11 Correct 560 ms 598068 KB Output is correct
12 Correct 542 ms 598004 KB Output is correct
13 Correct 541 ms 598008 KB Output is correct
14 Correct 566 ms 597924 KB Output is correct
15 Correct 607 ms 597888 KB Output is correct
16 Correct 556 ms 598136 KB Output is correct
17 Correct 546 ms 597948 KB Output is correct
18 Correct 540 ms 598140 KB Output is correct
19 Correct 546 ms 598228 KB Output is correct
20 Correct 587 ms 598044 KB Output is correct
21 Correct 551 ms 597984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 597996 KB Output is correct
2 Correct 546 ms 598136 KB Output is correct
3 Correct 543 ms 598008 KB Output is correct
4 Correct 553 ms 598008 KB Output is correct
5 Correct 538 ms 598008 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 540 ms 597920 KB Output is correct
8 Correct 542 ms 598092 KB Output is correct
9 Correct 541 ms 597996 KB Output is correct
10 Correct 542 ms 598076 KB Output is correct
11 Correct 560 ms 598068 KB Output is correct
12 Correct 542 ms 598004 KB Output is correct
13 Correct 541 ms 598008 KB Output is correct
14 Correct 566 ms 597924 KB Output is correct
15 Correct 607 ms 597888 KB Output is correct
16 Correct 556 ms 598136 KB Output is correct
17 Correct 545 ms 598480 KB Output is correct
18 Correct 593 ms 598492 KB Output is correct
19 Correct 541 ms 598264 KB Output is correct
20 Correct 586 ms 598124 KB Output is correct
21 Correct 544 ms 598388 KB Output is correct
22 Correct 580 ms 598392 KB Output is correct
23 Correct 546 ms 598352 KB Output is correct
24 Correct 543 ms 598264 KB Output is correct
25 Correct 546 ms 597948 KB Output is correct
26 Correct 540 ms 598140 KB Output is correct
27 Correct 546 ms 598228 KB Output is correct
28 Correct 587 ms 598044 KB Output is correct
29 Correct 551 ms 597984 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 597996 KB Output is correct
2 Correct 546 ms 598136 KB Output is correct
3 Correct 543 ms 598008 KB Output is correct
4 Correct 553 ms 598008 KB Output is correct
5 Correct 538 ms 598008 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 540 ms 597920 KB Output is correct
8 Correct 542 ms 598092 KB Output is correct
9 Correct 541 ms 597996 KB Output is correct
10 Correct 542 ms 598076 KB Output is correct
11 Correct 560 ms 598068 KB Output is correct
12 Correct 542 ms 598004 KB Output is correct
13 Correct 541 ms 598008 KB Output is correct
14 Correct 566 ms 597924 KB Output is correct
15 Correct 607 ms 597888 KB Output is correct
16 Correct 556 ms 598136 KB Output is correct
17 Correct 545 ms 598480 KB Output is correct
18 Correct 593 ms 598492 KB Output is correct
19 Correct 541 ms 598264 KB Output is correct
20 Correct 586 ms 598124 KB Output is correct
21 Correct 544 ms 598388 KB Output is correct
22 Correct 580 ms 598392 KB Output is correct
23 Correct 546 ms 598352 KB Output is correct
24 Correct 543 ms 598264 KB Output is correct
25 Correct 583 ms 600148 KB Output is correct
26 Correct 561 ms 600152 KB Output is correct
27 Correct 611 ms 600280 KB Output is correct
28 Correct 553 ms 599148 KB Output is correct
29 Correct 569 ms 600152 KB Output is correct
30 Correct 563 ms 600152 KB Output is correct
31 Correct 561 ms 600148 KB Output is correct
32 Correct 595 ms 599900 KB Output is correct
33 Correct 546 ms 597948 KB Output is correct
34 Correct 540 ms 598140 KB Output is correct
35 Correct 546 ms 598228 KB Output is correct
36 Correct 587 ms 598044 KB Output is correct
37 Correct 551 ms 597984 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 597996 KB Output is correct
2 Correct 546 ms 598136 KB Output is correct
3 Correct 543 ms 598008 KB Output is correct
4 Correct 553 ms 598008 KB Output is correct
5 Correct 538 ms 598008 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 540 ms 597920 KB Output is correct
8 Correct 542 ms 598092 KB Output is correct
9 Correct 541 ms 597996 KB Output is correct
10 Correct 542 ms 598076 KB Output is correct
11 Correct 560 ms 598068 KB Output is correct
12 Correct 542 ms 598004 KB Output is correct
13 Correct 541 ms 598008 KB Output is correct
14 Correct 566 ms 597924 KB Output is correct
15 Correct 607 ms 597888 KB Output is correct
16 Correct 556 ms 598136 KB Output is correct
17 Correct 545 ms 598480 KB Output is correct
18 Correct 593 ms 598492 KB Output is correct
19 Correct 541 ms 598264 KB Output is correct
20 Correct 586 ms 598124 KB Output is correct
21 Correct 544 ms 598388 KB Output is correct
22 Correct 580 ms 598392 KB Output is correct
23 Correct 546 ms 598352 KB Output is correct
24 Correct 543 ms 598264 KB Output is correct
25 Correct 583 ms 600148 KB Output is correct
26 Correct 561 ms 600152 KB Output is correct
27 Correct 611 ms 600280 KB Output is correct
28 Correct 553 ms 599148 KB Output is correct
29 Correct 569 ms 600152 KB Output is correct
30 Correct 563 ms 600152 KB Output is correct
31 Correct 561 ms 600148 KB Output is correct
32 Correct 595 ms 599900 KB Output is correct
33 Correct 675 ms 613568 KB Output is correct
34 Correct 659 ms 613460 KB Output is correct
35 Correct 681 ms 613440 KB Output is correct
36 Correct 667 ms 613488 KB Output is correct
37 Correct 781 ms 624880 KB Output is correct
38 Correct 788 ms 624752 KB Output is correct
39 Correct 785 ms 624880 KB Output is correct
40 Correct 772 ms 623088 KB Output is correct
41 Correct 646 ms 607612 KB Output is correct
42 Correct 685 ms 610876 KB Output is correct
43 Correct 823 ms 624372 KB Output is correct
44 Correct 829 ms 624568 KB Output is correct
45 Correct 678 ms 611388 KB Output is correct
46 Correct 682 ms 611256 KB Output is correct
47 Correct 804 ms 622716 KB Output is correct
48 Correct 814 ms 622868 KB Output is correct
49 Correct 546 ms 597948 KB Output is correct
50 Correct 540 ms 598140 KB Output is correct
51 Correct 546 ms 598228 KB Output is correct
52 Correct 587 ms 598044 KB Output is correct
53 Correct 551 ms 597984 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 598392 KB Output is correct
2 Correct 551 ms 598360 KB Output is correct
3 Correct 540 ms 598164 KB Output is correct
4 Correct 552 ms 598008 KB Output is correct
5 Correct 541 ms 598256 KB Output is correct
6 Correct 538 ms 598392 KB Output is correct
7 Correct 568 ms 598392 KB Output is correct
8 Correct 543 ms 598296 KB Output is correct
9 Correct 554 ms 598264 KB Output is correct
10 Correct 546 ms 598136 KB Output is correct
11 Correct 587 ms 598392 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 597900 KB Output is correct
2 Correct 1269 ms 650264 KB Output is correct
3 Correct 2200 ms 709808 KB Output is correct
4 Correct 2185 ms 710372 KB Output is correct
5 Correct 2195 ms 710348 KB Output is correct
6 Correct 742 ms 629368 KB Output is correct
7 Correct 945 ms 658460 KB Output is correct
8 Correct 958 ms 661524 KB Output is correct
9 Correct 546 ms 597948 KB Output is correct
10 Correct 540 ms 598140 KB Output is correct
11 Correct 546 ms 598228 KB Output is correct
12 Correct 587 ms 598044 KB Output is correct
13 Correct 551 ms 597984 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 597996 KB Output is correct
2 Correct 546 ms 598136 KB Output is correct
3 Correct 543 ms 598008 KB Output is correct
4 Correct 553 ms 598008 KB Output is correct
5 Correct 538 ms 598008 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 540 ms 597920 KB Output is correct
8 Correct 542 ms 598092 KB Output is correct
9 Correct 541 ms 597996 KB Output is correct
10 Correct 542 ms 598076 KB Output is correct
11 Correct 560 ms 598068 KB Output is correct
12 Correct 542 ms 598004 KB Output is correct
13 Correct 541 ms 598008 KB Output is correct
14 Correct 566 ms 597924 KB Output is correct
15 Correct 607 ms 597888 KB Output is correct
16 Correct 556 ms 598136 KB Output is correct
17 Correct 545 ms 598480 KB Output is correct
18 Correct 593 ms 598492 KB Output is correct
19 Correct 541 ms 598264 KB Output is correct
20 Correct 586 ms 598124 KB Output is correct
21 Correct 544 ms 598388 KB Output is correct
22 Correct 580 ms 598392 KB Output is correct
23 Correct 546 ms 598352 KB Output is correct
24 Correct 543 ms 598264 KB Output is correct
25 Correct 583 ms 600148 KB Output is correct
26 Correct 561 ms 600152 KB Output is correct
27 Correct 611 ms 600280 KB Output is correct
28 Correct 553 ms 599148 KB Output is correct
29 Correct 569 ms 600152 KB Output is correct
30 Correct 563 ms 600152 KB Output is correct
31 Correct 561 ms 600148 KB Output is correct
32 Correct 595 ms 599900 KB Output is correct
33 Correct 675 ms 613568 KB Output is correct
34 Correct 659 ms 613460 KB Output is correct
35 Correct 681 ms 613440 KB Output is correct
36 Correct 667 ms 613488 KB Output is correct
37 Correct 781 ms 624880 KB Output is correct
38 Correct 788 ms 624752 KB Output is correct
39 Correct 785 ms 624880 KB Output is correct
40 Correct 772 ms 623088 KB Output is correct
41 Correct 646 ms 607612 KB Output is correct
42 Correct 685 ms 610876 KB Output is correct
43 Correct 823 ms 624372 KB Output is correct
44 Correct 829 ms 624568 KB Output is correct
45 Correct 678 ms 611388 KB Output is correct
46 Correct 682 ms 611256 KB Output is correct
47 Correct 804 ms 622716 KB Output is correct
48 Correct 814 ms 622868 KB Output is correct
49 Correct 541 ms 598392 KB Output is correct
50 Correct 551 ms 598360 KB Output is correct
51 Correct 540 ms 598164 KB Output is correct
52 Correct 552 ms 598008 KB Output is correct
53 Correct 541 ms 598256 KB Output is correct
54 Correct 538 ms 598392 KB Output is correct
55 Correct 568 ms 598392 KB Output is correct
56 Correct 543 ms 598296 KB Output is correct
57 Correct 554 ms 598264 KB Output is correct
58 Correct 546 ms 598136 KB Output is correct
59 Correct 587 ms 598392 KB Output is correct
60 Correct 547 ms 597900 KB Output is correct
61 Correct 1269 ms 650264 KB Output is correct
62 Correct 2200 ms 709808 KB Output is correct
63 Correct 2185 ms 710372 KB Output is correct
64 Correct 2195 ms 710348 KB Output is correct
65 Correct 742 ms 629368 KB Output is correct
66 Correct 945 ms 658460 KB Output is correct
67 Correct 958 ms 661524 KB Output is correct
68 Correct 2323 ms 784004 KB Output is correct
69 Correct 2158 ms 784104 KB Output is correct
70 Correct 3030 ms 784272 KB Output is correct
71 Correct 2500 ms 784372 KB Output is correct
72 Correct 3922 ms 930524 KB Output is correct
73 Correct 3126 ms 793796 KB Output is correct
74 Correct 3237 ms 812368 KB Output is correct
75 Correct 4898 ms 924852 KB Output is correct
76 Correct 3169 ms 796080 KB Output is correct
77 Correct 3984 ms 865700 KB Output is correct
78 Correct 4969 ms 928956 KB Output is correct
79 Correct 2895 ms 782656 KB Output is correct
80 Correct 4709 ms 908548 KB Output is correct
81 Correct 4755 ms 899348 KB Output is correct
82 Correct 2625 ms 803260 KB Output is correct
83 Correct 3898 ms 930276 KB Output is correct
84 Correct 3895 ms 930548 KB Output is correct
85 Correct 3935 ms 930520 KB Output is correct
86 Correct 546 ms 597948 KB Output is correct
87 Correct 540 ms 598140 KB Output is correct
88 Correct 546 ms 598228 KB Output is correct
89 Correct 587 ms 598044 KB Output is correct
90 Correct 551 ms 597984 KB Output is correct