oj.uz

Submission #144740

# Submission time Handle Problem Language Result Execution time Memory
144740 2019-08-17T15:42:02 Z nvmdava Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 930552 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define N 2501

map<int, int> cnt[2][N][N];
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[i1][i2][r - 1][r - l - 1]++;
		else 
			cnt[i1][r - 1][i2][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;

long long count_rectangles(vector<vector<int> > a){
	n = a.size();
	m = a[0].size();
	
	memset(arr, 0x3f, sizeof arr);

	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++){
			sad.clear();
			for(auto& x : cnt[0][i][j]){
				auto it = cnt[0][i - 1][j].find(x.ff);
				if(it != cnt[0][i - 1][j].end())
					x.ss = 1 + it -> ss;
				sad.push_back({x.ss, x.ff});
				update(x.ff, 1);
			}
			sort(sad.rbegin(), sad.rend());
			int i1 = sad.size() - 1;
			for(auto& x : cnt[1][i][j]){
				auto it = cnt[1][i][j - 1].find(x.ff);
				if(it != cnt[1][i][j - 1].end())
					x.ss = 1 + it -> ss;

				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[0][i - 1][j].clear();
			cnt[1][i - 1][j].clear();
		}
	}
	return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 612472 KB Output is correct
2 Correct 558 ms 612392 KB Output is correct
3 Correct 555 ms 612388 KB Output is correct
4 Correct 569 ms 612392 KB Output is correct
5 Correct 553 ms 612436 KB Output is correct
6 Correct 553 ms 612560 KB Output is correct
7 Correct 552 ms 612472 KB Output is correct
8 Correct 551 ms 612412 KB Output is correct
9 Correct 570 ms 612600 KB Output is correct
10 Correct 559 ms 612472 KB Output is correct
11 Correct 559 ms 612472 KB Output is correct
12 Correct 556 ms 612440 KB Output is correct
13 Correct 552 ms 612368 KB Output is correct
14 Correct 552 ms 612484 KB Output is correct
15 Correct 556 ms 612444 KB Output is correct
16 Correct 558 ms 612404 KB Output is correct
17 Correct 603 ms 612368 KB Output is correct
18 Correct 554 ms 612352 KB Output is correct
19 Correct 562 ms 612352 KB Output is correct
20 Correct 553 ms 612364 KB Output is correct
21 Correct 605 ms 612472 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 612472 KB Output is correct
2 Correct 558 ms 612392 KB Output is correct
3 Correct 555 ms 612388 KB Output is correct
4 Correct 569 ms 612392 KB Output is correct
5 Correct 553 ms 612436 KB Output is correct
6 Correct 553 ms 612560 KB Output is correct
7 Correct 552 ms 612472 KB Output is correct
8 Correct 551 ms 612412 KB Output is correct
9 Correct 570 ms 612600 KB Output is correct
10 Correct 559 ms 612472 KB Output is correct
11 Correct 559 ms 612472 KB Output is correct
12 Correct 556 ms 612440 KB Output is correct
13 Correct 552 ms 612368 KB Output is correct
14 Correct 552 ms 612484 KB Output is correct
15 Correct 556 ms 612444 KB Output is correct
16 Correct 558 ms 612404 KB Output is correct
17 Correct 557 ms 612752 KB Output is correct
18 Correct 555 ms 612728 KB Output is correct
19 Correct 561 ms 612824 KB Output is correct
20 Correct 555 ms 612452 KB Output is correct
21 Correct 559 ms 612812 KB Output is correct
22 Correct 556 ms 612624 KB Output is correct
23 Correct 559 ms 612660 KB Output is correct
24 Correct 559 ms 612764 KB Output is correct
25 Correct 603 ms 612368 KB Output is correct
26 Correct 554 ms 612352 KB Output is correct
27 Correct 562 ms 612352 KB Output is correct
28 Correct 553 ms 612364 KB Output is correct
29 Correct 605 ms 612472 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 612472 KB Output is correct
2 Correct 558 ms 612392 KB Output is correct
3 Correct 555 ms 612388 KB Output is correct
4 Correct 569 ms 612392 KB Output is correct
5 Correct 553 ms 612436 KB Output is correct
6 Correct 553 ms 612560 KB Output is correct
7 Correct 552 ms 612472 KB Output is correct
8 Correct 551 ms 612412 KB Output is correct
9 Correct 570 ms 612600 KB Output is correct
10 Correct 559 ms 612472 KB Output is correct
11 Correct 559 ms 612472 KB Output is correct
12 Correct 556 ms 612440 KB Output is correct
13 Correct 552 ms 612368 KB Output is correct
14 Correct 552 ms 612484 KB Output is correct
15 Correct 556 ms 612444 KB Output is correct
16 Correct 558 ms 612404 KB Output is correct
17 Correct 557 ms 612752 KB Output is correct
18 Correct 555 ms 612728 KB Output is correct
19 Correct 561 ms 612824 KB Output is correct
20 Correct 555 ms 612452 KB Output is correct
21 Correct 559 ms 612812 KB Output is correct
22 Correct 556 ms 612624 KB Output is correct
23 Correct 559 ms 612660 KB Output is correct
24 Correct 559 ms 612764 KB Output is correct
25 Correct 569 ms 614544 KB Output is correct
26 Correct 572 ms 614476 KB Output is correct
27 Correct 573 ms 614460 KB Output is correct
28 Correct 575 ms 613248 KB Output is correct
29 Correct 574 ms 614360 KB Output is correct
30 Correct 572 ms 614332 KB Output is correct
31 Correct 577 ms 614360 KB Output is correct
32 Correct 571 ms 614280 KB Output is correct
33 Correct 603 ms 612368 KB Output is correct
34 Correct 554 ms 612352 KB Output is correct
35 Correct 562 ms 612352 KB Output is correct
36 Correct 553 ms 612364 KB Output is correct
37 Correct 605 ms 612472 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 612472 KB Output is correct
2 Correct 558 ms 612392 KB Output is correct
3 Correct 555 ms 612388 KB Output is correct
4 Correct 569 ms 612392 KB Output is correct
5 Correct 553 ms 612436 KB Output is correct
6 Correct 553 ms 612560 KB Output is correct
7 Correct 552 ms 612472 KB Output is correct
8 Correct 551 ms 612412 KB Output is correct
9 Correct 570 ms 612600 KB Output is correct
10 Correct 559 ms 612472 KB Output is correct
11 Correct 559 ms 612472 KB Output is correct
12 Correct 556 ms 612440 KB Output is correct
13 Correct 552 ms 612368 KB Output is correct
14 Correct 552 ms 612484 KB Output is correct
15 Correct 556 ms 612444 KB Output is correct
16 Correct 558 ms 612404 KB Output is correct
17 Correct 557 ms 612752 KB Output is correct
18 Correct 555 ms 612728 KB Output is correct
19 Correct 561 ms 612824 KB Output is correct
20 Correct 555 ms 612452 KB Output is correct
21 Correct 559 ms 612812 KB Output is correct
22 Correct 556 ms 612624 KB Output is correct
23 Correct 559 ms 612660 KB Output is correct
24 Correct 559 ms 612764 KB Output is correct
25 Correct 569 ms 614544 KB Output is correct
26 Correct 572 ms 614476 KB Output is correct
27 Correct 573 ms 614460 KB Output is correct
28 Correct 575 ms 613248 KB Output is correct
29 Correct 574 ms 614360 KB Output is correct
30 Correct 572 ms 614332 KB Output is correct
31 Correct 577 ms 614360 KB Output is correct
32 Correct 571 ms 614280 KB Output is correct
33 Correct 678 ms 626020 KB Output is correct
34 Correct 673 ms 626032 KB Output is correct
35 Correct 694 ms 626032 KB Output is correct
36 Correct 681 ms 626004 KB Output is correct
37 Correct 819 ms 637476 KB Output is correct
38 Correct 819 ms 637388 KB Output is correct
39 Correct 817 ms 637320 KB Output is correct
40 Correct 802 ms 635844 KB Output is correct
41 Correct 658 ms 620080 KB Output is correct
42 Correct 700 ms 623292 KB Output is correct
43 Correct 859 ms 636808 KB Output is correct
44 Correct 855 ms 637040 KB Output is correct
45 Correct 693 ms 624768 KB Output is correct
46 Correct 696 ms 624588 KB Output is correct
47 Correct 834 ms 635288 KB Output is correct
48 Correct 837 ms 635284 KB Output is correct
49 Correct 603 ms 612368 KB Output is correct
50 Correct 554 ms 612352 KB Output is correct
51 Correct 562 ms 612352 KB Output is correct
52 Correct 553 ms 612364 KB Output is correct
53 Correct 605 ms 612472 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 612856 KB Output is correct
2 Correct 554 ms 612736 KB Output is correct
3 Correct 580 ms 612436 KB Output is correct
4 Correct 556 ms 612372 KB Output is correct
5 Correct 554 ms 612728 KB Output is correct
6 Correct 557 ms 612668 KB Output is correct
7 Correct 559 ms 612788 KB Output is correct
8 Correct 567 ms 612756 KB Output is correct
9 Correct 575 ms 612620 KB Output is correct
10 Correct 555 ms 612600 KB Output is correct
11 Correct 562 ms 612572 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 612376 KB Output is correct
2 Correct 1257 ms 657452 KB Output is correct
3 Correct 2304 ms 709836 KB Output is correct
4 Correct 2164 ms 710364 KB Output is correct
5 Correct 2256 ms 710376 KB Output is correct
6 Correct 763 ms 636652 KB Output is correct
7 Correct 946 ms 658396 KB Output is correct
8 Correct 962 ms 661704 KB Output is correct
9 Correct 603 ms 612368 KB Output is correct
10 Correct 554 ms 612352 KB Output is correct
11 Correct 562 ms 612352 KB Output is correct
12 Correct 553 ms 612364 KB Output is correct
13 Correct 605 ms 612472 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 612472 KB Output is correct
2 Correct 558 ms 612392 KB Output is correct
3 Correct 555 ms 612388 KB Output is correct
4 Correct 569 ms 612392 KB Output is correct
5 Correct 553 ms 612436 KB Output is correct
6 Correct 553 ms 612560 KB Output is correct
7 Correct 552 ms 612472 KB Output is correct
8 Correct 551 ms 612412 KB Output is correct
9 Correct 570 ms 612600 KB Output is correct
10 Correct 559 ms 612472 KB Output is correct
11 Correct 559 ms 612472 KB Output is correct
12 Correct 556 ms 612440 KB Output is correct
13 Correct 552 ms 612368 KB Output is correct
14 Correct 552 ms 612484 KB Output is correct
15 Correct 556 ms 612444 KB Output is correct
16 Correct 558 ms 612404 KB Output is correct
17 Correct 557 ms 612752 KB Output is correct
18 Correct 555 ms 612728 KB Output is correct
19 Correct 561 ms 612824 KB Output is correct
20 Correct 555 ms 612452 KB Output is correct
21 Correct 559 ms 612812 KB Output is correct
22 Correct 556 ms 612624 KB Output is correct
23 Correct 559 ms 612660 KB Output is correct
24 Correct 559 ms 612764 KB Output is correct
25 Correct 569 ms 614544 KB Output is correct
26 Correct 572 ms 614476 KB Output is correct
27 Correct 573 ms 614460 KB Output is correct
28 Correct 575 ms 613248 KB Output is correct
29 Correct 574 ms 614360 KB Output is correct
30 Correct 572 ms 614332 KB Output is correct
31 Correct 577 ms 614360 KB Output is correct
32 Correct 571 ms 614280 KB Output is correct
33 Correct 678 ms 626020 KB Output is correct
34 Correct 673 ms 626032 KB Output is correct
35 Correct 694 ms 626032 KB Output is correct
36 Correct 681 ms 626004 KB Output is correct
37 Correct 819 ms 637476 KB Output is correct
38 Correct 819 ms 637388 KB Output is correct
39 Correct 817 ms 637320 KB Output is correct
40 Correct 802 ms 635844 KB Output is correct
41 Correct 658 ms 620080 KB Output is correct
42 Correct 700 ms 623292 KB Output is correct
43 Correct 859 ms 636808 KB Output is correct
44 Correct 855 ms 637040 KB Output is correct
45 Correct 693 ms 624768 KB Output is correct
46 Correct 696 ms 624588 KB Output is correct
47 Correct 834 ms 635288 KB Output is correct
48 Correct 837 ms 635284 KB Output is correct
49 Correct 561 ms 612856 KB Output is correct
50 Correct 554 ms 612736 KB Output is correct
51 Correct 580 ms 612436 KB Output is correct
52 Correct 556 ms 612372 KB Output is correct
53 Correct 554 ms 612728 KB Output is correct
54 Correct 557 ms 612668 KB Output is correct
55 Correct 559 ms 612788 KB Output is correct
56 Correct 567 ms 612756 KB Output is correct
57 Correct 575 ms 612620 KB Output is correct
58 Correct 555 ms 612600 KB Output is correct
59 Correct 562 ms 612572 KB Output is correct
60 Correct 560 ms 612376 KB Output is correct
61 Correct 1257 ms 657452 KB Output is correct
62 Correct 2304 ms 709836 KB Output is correct
63 Correct 2164 ms 710364 KB Output is correct
64 Correct 2256 ms 710376 KB Output is correct
65 Correct 763 ms 636652 KB Output is correct
66 Correct 946 ms 658396 KB Output is correct
67 Correct 962 ms 661704 KB Output is correct
68 Correct 2343 ms 784040 KB Output is correct
69 Correct 2230 ms 784036 KB Output is correct
70 Correct 2828 ms 784288 KB Output is correct
71 Correct 2506 ms 784252 KB Output is correct
72 Correct 4235 ms 930552 KB Output is correct
73 Correct 3223 ms 799464 KB Output is correct
74 Correct 3388 ms 812364 KB Output is correct
75 Correct 4986 ms 924872 KB Output is correct
76 Correct 3213 ms 801876 KB Output is correct
77 Correct 4119 ms 865696 KB Output is correct
78 Execution timed out 5054 ms 929148 KB Time limit exceeded
79 Halted 0 ms 0 KB -