oj.uz

Submission #144755

# Submission time Handle Problem Language Result Execution time Memory
144755 2019-08-17T15:56:07 Z nvmdava Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 930632 KB 
#include "rect.h"
#pragma GCC optimize("-Ofast")
#pragma GCC target("avx,avx2,fma")
#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;
int i1;
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());
			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 559 ms 612416 KB Output is correct
2 Correct 562 ms 612512 KB Output is correct
3 Correct 563 ms 612476 KB Output is correct
4 Correct 569 ms 612648 KB Output is correct
5 Correct 556 ms 612400 KB Output is correct
6 Correct 564 ms 612600 KB Output is correct
7 Correct 564 ms 612348 KB Output is correct
8 Correct 566 ms 612548 KB Output is correct
9 Correct 571 ms 612492 KB Output is correct
10 Correct 595 ms 612504 KB Output is correct
11 Correct 565 ms 612524 KB Output is correct
12 Correct 561 ms 612536 KB Output is correct
13 Correct 586 ms 612504 KB Output is correct
14 Correct 588 ms 612380 KB Output is correct
15 Correct 568 ms 612476 KB Output is correct
16 Correct 595 ms 612472 KB Output is correct
17 Correct 611 ms 612472 KB Output is correct
18 Correct 603 ms 612456 KB Output is correct
19 Correct 584 ms 612524 KB Output is correct
20 Correct 565 ms 612496 KB Output is correct
21 Correct 576 ms 612564 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 612416 KB Output is correct
2 Correct 562 ms 612512 KB Output is correct
3 Correct 563 ms 612476 KB Output is correct
4 Correct 569 ms 612648 KB Output is correct
5 Correct 556 ms 612400 KB Output is correct
6 Correct 564 ms 612600 KB Output is correct
7 Correct 564 ms 612348 KB Output is correct
8 Correct 566 ms 612548 KB Output is correct
9 Correct 571 ms 612492 KB Output is correct
10 Correct 595 ms 612504 KB Output is correct
11 Correct 565 ms 612524 KB Output is correct
12 Correct 561 ms 612536 KB Output is correct
13 Correct 586 ms 612504 KB Output is correct
14 Correct 588 ms 612380 KB Output is correct
15 Correct 568 ms 612476 KB Output is correct
16 Correct 595 ms 612472 KB Output is correct
17 Correct 564 ms 612748 KB Output is correct
18 Correct 561 ms 612700 KB Output is correct
19 Correct 563 ms 612776 KB Output is correct
20 Correct 563 ms 612572 KB Output is correct
21 Correct 566 ms 612808 KB Output is correct
22 Correct 568 ms 612728 KB Output is correct
23 Correct 568 ms 612684 KB Output is correct
24 Correct 560 ms 612584 KB Output is correct
25 Correct 611 ms 612472 KB Output is correct
26 Correct 603 ms 612456 KB Output is correct
27 Correct 584 ms 612524 KB Output is correct
28 Correct 565 ms 612496 KB Output is correct
29 Correct 576 ms 612564 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 612416 KB Output is correct
2 Correct 562 ms 612512 KB Output is correct
3 Correct 563 ms 612476 KB Output is correct
4 Correct 569 ms 612648 KB Output is correct
5 Correct 556 ms 612400 KB Output is correct
6 Correct 564 ms 612600 KB Output is correct
7 Correct 564 ms 612348 KB Output is correct
8 Correct 566 ms 612548 KB Output is correct
9 Correct 571 ms 612492 KB Output is correct
10 Correct 595 ms 612504 KB Output is correct
11 Correct 565 ms 612524 KB Output is correct
12 Correct 561 ms 612536 KB Output is correct
13 Correct 586 ms 612504 KB Output is correct
14 Correct 588 ms 612380 KB Output is correct
15 Correct 568 ms 612476 KB Output is correct
16 Correct 595 ms 612472 KB Output is correct
17 Correct 564 ms 612748 KB Output is correct
18 Correct 561 ms 612700 KB Output is correct
19 Correct 563 ms 612776 KB Output is correct
20 Correct 563 ms 612572 KB Output is correct
21 Correct 566 ms 612808 KB Output is correct
22 Correct 568 ms 612728 KB Output is correct
23 Correct 568 ms 612684 KB Output is correct
24 Correct 560 ms 612584 KB Output is correct
25 Correct 587 ms 614388 KB Output is correct
26 Correct 588 ms 614472 KB Output is correct
27 Correct 585 ms 614508 KB Output is correct
28 Correct 572 ms 613444 KB Output is correct
29 Correct 583 ms 614368 KB Output is correct
30 Correct 585 ms 614360 KB Output is correct
31 Correct 583 ms 614300 KB Output is correct
32 Correct 604 ms 614236 KB Output is correct
33 Correct 611 ms 612472 KB Output is correct
34 Correct 603 ms 612456 KB Output is correct
35 Correct 584 ms 612524 KB Output is correct
36 Correct 565 ms 612496 KB Output is correct
37 Correct 576 ms 612564 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 612416 KB Output is correct
2 Correct 562 ms 612512 KB Output is correct
3 Correct 563 ms 612476 KB Output is correct
4 Correct 569 ms 612648 KB Output is correct
5 Correct 556 ms 612400 KB Output is correct
6 Correct 564 ms 612600 KB Output is correct
7 Correct 564 ms 612348 KB Output is correct
8 Correct 566 ms 612548 KB Output is correct
9 Correct 571 ms 612492 KB Output is correct
10 Correct 595 ms 612504 KB Output is correct
11 Correct 565 ms 612524 KB Output is correct
12 Correct 561 ms 612536 KB Output is correct
13 Correct 586 ms 612504 KB Output is correct
14 Correct 588 ms 612380 KB Output is correct
15 Correct 568 ms 612476 KB Output is correct
16 Correct 595 ms 612472 KB Output is correct
17 Correct 564 ms 612748 KB Output is correct
18 Correct 561 ms 612700 KB Output is correct
19 Correct 563 ms 612776 KB Output is correct
20 Correct 563 ms 612572 KB Output is correct
21 Correct 566 ms 612808 KB Output is correct
22 Correct 568 ms 612728 KB Output is correct
23 Correct 568 ms 612684 KB Output is correct
24 Correct 560 ms 612584 KB Output is correct
25 Correct 587 ms 614388 KB Output is correct
26 Correct 588 ms 614472 KB Output is correct
27 Correct 585 ms 614508 KB Output is correct
28 Correct 572 ms 613444 KB Output is correct
29 Correct 583 ms 614368 KB Output is correct
30 Correct 585 ms 614360 KB Output is correct
31 Correct 583 ms 614300 KB Output is correct
32 Correct 604 ms 614236 KB Output is correct
33 Correct 738 ms 626008 KB Output is correct
34 Correct 734 ms 625912 KB Output is correct
35 Correct 716 ms 626160 KB Output is correct
36 Correct 696 ms 626004 KB Output is correct
37 Correct 836 ms 637528 KB Output is correct
38 Correct 834 ms 637296 KB Output is correct
39 Correct 836 ms 637452 KB Output is correct
40 Correct 821 ms 635884 KB Output is correct
41 Correct 681 ms 620272 KB Output is correct
42 Correct 711 ms 623580 KB Output is correct
43 Correct 947 ms 636832 KB Output is correct
44 Correct 868 ms 637296 KB Output is correct
45 Correct 706 ms 625076 KB Output is correct
46 Correct 715 ms 624648 KB Output is correct
47 Correct 841 ms 635072 KB Output is correct
48 Correct 849 ms 635380 KB Output is correct
49 Correct 611 ms 612472 KB Output is correct
50 Correct 603 ms 612456 KB Output is correct
51 Correct 584 ms 612524 KB Output is correct
52 Correct 565 ms 612496 KB Output is correct
53 Correct 576 ms 612564 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 613112 KB Output is correct
2 Correct 595 ms 612860 KB Output is correct
3 Correct 562 ms 612636 KB Output is correct
4 Correct 561 ms 612364 KB Output is correct
5 Correct 606 ms 612816 KB Output is correct
6 Correct 569 ms 612728 KB Output is correct
7 Correct 563 ms 612736 KB Output is correct
8 Correct 568 ms 612740 KB Output is correct
9 Correct 570 ms 612744 KB Output is correct
10 Correct 585 ms 612524 KB Output is correct
11 Correct 567 ms 612660 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 612360 KB Output is correct
2 Correct 1319 ms 657388 KB Output is correct
3 Correct 2324 ms 710100 KB Output is correct
4 Correct 2400 ms 710504 KB Output is correct
5 Correct 2318 ms 710552 KB Output is correct
6 Correct 774 ms 636580 KB Output is correct
7 Correct 1010 ms 658428 KB Output is correct
8 Correct 1006 ms 661752 KB Output is correct
9 Correct 611 ms 612472 KB Output is correct
10 Correct 603 ms 612456 KB Output is correct
11 Correct 584 ms 612524 KB Output is correct
12 Correct 565 ms 612496 KB Output is correct
13 Correct 576 ms 612564 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 612416 KB Output is correct
2 Correct 562 ms 612512 KB Output is correct
3 Correct 563 ms 612476 KB Output is correct
4 Correct 569 ms 612648 KB Output is correct
5 Correct 556 ms 612400 KB Output is correct
6 Correct 564 ms 612600 KB Output is correct
7 Correct 564 ms 612348 KB Output is correct
8 Correct 566 ms 612548 KB Output is correct
9 Correct 571 ms 612492 KB Output is correct
10 Correct 595 ms 612504 KB Output is correct
11 Correct 565 ms 612524 KB Output is correct
12 Correct 561 ms 612536 KB Output is correct
13 Correct 586 ms 612504 KB Output is correct
14 Correct 588 ms 612380 KB Output is correct
15 Correct 568 ms 612476 KB Output is correct
16 Correct 595 ms 612472 KB Output is correct
17 Correct 564 ms 612748 KB Output is correct
18 Correct 561 ms 612700 KB Output is correct
19 Correct 563 ms 612776 KB Output is correct
20 Correct 563 ms 612572 KB Output is correct
21 Correct 566 ms 612808 KB Output is correct
22 Correct 568 ms 612728 KB Output is correct
23 Correct 568 ms 612684 KB Output is correct
24 Correct 560 ms 612584 KB Output is correct
25 Correct 587 ms 614388 KB Output is correct
26 Correct 588 ms 614472 KB Output is correct
27 Correct 585 ms 614508 KB Output is correct
28 Correct 572 ms 613444 KB Output is correct
29 Correct 583 ms 614368 KB Output is correct
30 Correct 585 ms 614360 KB Output is correct
31 Correct 583 ms 614300 KB Output is correct
32 Correct 604 ms 614236 KB Output is correct
33 Correct 738 ms 626008 KB Output is correct
34 Correct 734 ms 625912 KB Output is correct
35 Correct 716 ms 626160 KB Output is correct
36 Correct 696 ms 626004 KB Output is correct
37 Correct 836 ms 637528 KB Output is correct
38 Correct 834 ms 637296 KB Output is correct
39 Correct 836 ms 637452 KB Output is correct
40 Correct 821 ms 635884 KB Output is correct
41 Correct 681 ms 620272 KB Output is correct
42 Correct 711 ms 623580 KB Output is correct
43 Correct 947 ms 636832 KB Output is correct
44 Correct 868 ms 637296 KB Output is correct
45 Correct 706 ms 625076 KB Output is correct
46 Correct 715 ms 624648 KB Output is correct
47 Correct 841 ms 635072 KB Output is correct
48 Correct 849 ms 635380 KB Output is correct
49 Correct 590 ms 613112 KB Output is correct
50 Correct 595 ms 612860 KB Output is correct
51 Correct 562 ms 612636 KB Output is correct
52 Correct 561 ms 612364 KB Output is correct
53 Correct 606 ms 612816 KB Output is correct
54 Correct 569 ms 612728 KB Output is correct
55 Correct 563 ms 612736 KB Output is correct
56 Correct 568 ms 612740 KB Output is correct
57 Correct 570 ms 612744 KB Output is correct
58 Correct 585 ms 612524 KB Output is correct
59 Correct 567 ms 612660 KB Output is correct
60 Correct 559 ms 612360 KB Output is correct
61 Correct 1319 ms 657388 KB Output is correct
62 Correct 2324 ms 710100 KB Output is correct
63 Correct 2400 ms 710504 KB Output is correct
64 Correct 2318 ms 710552 KB Output is correct
65 Correct 774 ms 636580 KB Output is correct
66 Correct 1010 ms 658428 KB Output is correct
67 Correct 1006 ms 661752 KB Output is correct
68 Correct 2230 ms 783828 KB Output is correct
69 Correct 2293 ms 783848 KB Output is correct
70 Correct 2858 ms 784116 KB Output is correct
71 Correct 2673 ms 784276 KB Output is correct
72 Correct 4321 ms 930632 KB Output is correct
73 Correct 3351 ms 799564 KB Output is correct
74 Correct 3462 ms 812340 KB Output is correct
75 Execution timed out 5148 ms 924860 KB Time limit exceeded
76 Halted 0 ms 0 KB -