oj.uz

답안 #144762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144762 2019-08-17T16:05:33 Z nvmdava Rectangles (IOI19_rect) C++17
100 / 100
 4955 ms 930640 KB 
#include "rect.h"
#pragma GCC optimize("-Ofast")
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 543 ms 598136 KB Output is correct
2 Correct 544 ms 597932 KB Output is correct
3 Correct 549 ms 598228 KB Output is correct
4 Correct 541 ms 598008 KB Output is correct
5 Correct 546 ms 597968 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 550 ms 598008 KB Output is correct
8 Correct 579 ms 598032 KB Output is correct
9 Correct 552 ms 598176 KB Output is correct
10 Correct 567 ms 598124 KB Output is correct
11 Correct 588 ms 598116 KB Output is correct
12 Correct 545 ms 598100 KB Output is correct
13 Correct 544 ms 598008 KB Output is correct
14 Correct 551 ms 598008 KB Output is correct
15 Correct 547 ms 598020 KB Output is correct
16 Correct 544 ms 598008 KB Output is correct
17 Correct 548 ms 597916 KB Output is correct
18 Correct 596 ms 598008 KB Output is correct
19 Correct 556 ms 598008 KB Output is correct
20 Correct 547 ms 597988 KB Output is correct
21 Correct 576 ms 598140 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 543 ms 598136 KB Output is correct
2 Correct 544 ms 597932 KB Output is correct
3 Correct 549 ms 598228 KB Output is correct
4 Correct 541 ms 598008 KB Output is correct
5 Correct 546 ms 597968 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 550 ms 598008 KB Output is correct
8 Correct 579 ms 598032 KB Output is correct
9 Correct 552 ms 598176 KB Output is correct
10 Correct 567 ms 598124 KB Output is correct
11 Correct 588 ms 598116 KB Output is correct
12 Correct 545 ms 598100 KB Output is correct
13 Correct 544 ms 598008 KB Output is correct
14 Correct 551 ms 598008 KB Output is correct
15 Correct 547 ms 598020 KB Output is correct
16 Correct 544 ms 598008 KB Output is correct
17 Correct 550 ms 598320 KB Output is correct
18 Correct 544 ms 598324 KB Output is correct
19 Correct 547 ms 598264 KB Output is correct
20 Correct 563 ms 598392 KB Output is correct
21 Correct 559 ms 598292 KB Output is correct
22 Correct 545 ms 598392 KB Output is correct
23 Correct 549 ms 598380 KB Output is correct
24 Correct 581 ms 598136 KB Output is correct
25 Correct 548 ms 597916 KB Output is correct
26 Correct 596 ms 598008 KB Output is correct
27 Correct 556 ms 598008 KB Output is correct
28 Correct 547 ms 597988 KB Output is correct
29 Correct 576 ms 598140 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 543 ms 598136 KB Output is correct
2 Correct 544 ms 597932 KB Output is correct
3 Correct 549 ms 598228 KB Output is correct
4 Correct 541 ms 598008 KB Output is correct
5 Correct 546 ms 597968 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 550 ms 598008 KB Output is correct
8 Correct 579 ms 598032 KB Output is correct
9 Correct 552 ms 598176 KB Output is correct
10 Correct 567 ms 598124 KB Output is correct
11 Correct 588 ms 598116 KB Output is correct
12 Correct 545 ms 598100 KB Output is correct
13 Correct 544 ms 598008 KB Output is correct
14 Correct 551 ms 598008 KB Output is correct
15 Correct 547 ms 598020 KB Output is correct
16 Correct 544 ms 598008 KB Output is correct
17 Correct 550 ms 598320 KB Output is correct
18 Correct 544 ms 598324 KB Output is correct
19 Correct 547 ms 598264 KB Output is correct
20 Correct 563 ms 598392 KB Output is correct
21 Correct 559 ms 598292 KB Output is correct
22 Correct 545 ms 598392 KB Output is correct
23 Correct 549 ms 598380 KB Output is correct
24 Correct 581 ms 598136 KB Output is correct
25 Correct 563 ms 600136 KB Output is correct
26 Correct 557 ms 600300 KB Output is correct
27 Correct 565 ms 600416 KB Output is correct
28 Correct 556 ms 599020 KB Output is correct
29 Correct 580 ms 600168 KB Output is correct
30 Correct 586 ms 600172 KB Output is correct
31 Correct 570 ms 600152 KB Output is correct
32 Correct 571 ms 600156 KB Output is correct
33 Correct 548 ms 597916 KB Output is correct
34 Correct 596 ms 598008 KB Output is correct
35 Correct 556 ms 598008 KB Output is correct
36 Correct 547 ms 597988 KB Output is correct
37 Correct 576 ms 598140 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 543 ms 598136 KB Output is correct
2 Correct 544 ms 597932 KB Output is correct
3 Correct 549 ms 598228 KB Output is correct
4 Correct 541 ms 598008 KB Output is correct
5 Correct 546 ms 597968 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 550 ms 598008 KB Output is correct
8 Correct 579 ms 598032 KB Output is correct
9 Correct 552 ms 598176 KB Output is correct
10 Correct 567 ms 598124 KB Output is correct
11 Correct 588 ms 598116 KB Output is correct
12 Correct 545 ms 598100 KB Output is correct
13 Correct 544 ms 598008 KB Output is correct
14 Correct 551 ms 598008 KB Output is correct
15 Correct 547 ms 598020 KB Output is correct
16 Correct 544 ms 598008 KB Output is correct
17 Correct 550 ms 598320 KB Output is correct
18 Correct 544 ms 598324 KB Output is correct
19 Correct 547 ms 598264 KB Output is correct
20 Correct 563 ms 598392 KB Output is correct
21 Correct 559 ms 598292 KB Output is correct
22 Correct 545 ms 598392 KB Output is correct
23 Correct 549 ms 598380 KB Output is correct
24 Correct 581 ms 598136 KB Output is correct
25 Correct 563 ms 600136 KB Output is correct
26 Correct 557 ms 600300 KB Output is correct
27 Correct 565 ms 600416 KB Output is correct
28 Correct 556 ms 599020 KB Output is correct
29 Correct 580 ms 600168 KB Output is correct
30 Correct 586 ms 600172 KB Output is correct
31 Correct 570 ms 600152 KB Output is correct
32 Correct 571 ms 600156 KB Output is correct
33 Correct 678 ms 613396 KB Output is correct
34 Correct 698 ms 613488 KB Output is correct
35 Correct 689 ms 613488 KB Output is correct
36 Correct 669 ms 613488 KB Output is correct
37 Correct 803 ms 625112 KB Output is correct
38 Correct 789 ms 624936 KB Output is correct
39 Correct 791 ms 624868 KB Output is correct
40 Correct 772 ms 623124 KB Output is correct
41 Correct 660 ms 607632 KB Output is correct
42 Correct 688 ms 611052 KB Output is correct
43 Correct 830 ms 624372 KB Output is correct
44 Correct 835 ms 624720 KB Output is correct
45 Correct 691 ms 611692 KB Output is correct
46 Correct 685 ms 611136 KB Output is correct
47 Correct 821 ms 622744 KB Output is correct
48 Correct 899 ms 622900 KB Output is correct
49 Correct 548 ms 597916 KB Output is correct
50 Correct 596 ms 598008 KB Output is correct
51 Correct 556 ms 598008 KB Output is correct
52 Correct 547 ms 597988 KB Output is correct
53 Correct 576 ms 598140 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 552 ms 598524 KB Output is correct
2 Correct 548 ms 598448 KB Output is correct
3 Correct 547 ms 598116 KB Output is correct
4 Correct 549 ms 598100 KB Output is correct
5 Correct 553 ms 598264 KB Output is correct
6 Correct 571 ms 598392 KB Output is correct
7 Correct 546 ms 598456 KB Output is correct
8 Correct 549 ms 598404 KB Output is correct
9 Correct 547 ms 598416 KB Output is correct
10 Correct 558 ms 598264 KB Output is correct
11 Correct 546 ms 598428 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 559 ms 597980 KB Output is correct
2 Correct 1325 ms 650148 KB Output is correct
3 Correct 2199 ms 710096 KB Output is correct
4 Correct 2197 ms 710472 KB Output is correct
5 Correct 2210 ms 710576 KB Output is correct
6 Correct 760 ms 629248 KB Output is correct
7 Correct 973 ms 658424 KB Output is correct
8 Correct 1004 ms 661712 KB Output is correct
9 Correct 548 ms 597916 KB Output is correct
10 Correct 596 ms 598008 KB Output is correct
11 Correct 556 ms 598008 KB Output is correct
12 Correct 547 ms 597988 KB Output is correct
13 Correct 576 ms 598140 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 543 ms 598136 KB Output is correct
2 Correct 544 ms 597932 KB Output is correct
3 Correct 549 ms 598228 KB Output is correct
4 Correct 541 ms 598008 KB Output is correct
5 Correct 546 ms 597968 KB Output is correct
6 Correct 541 ms 598008 KB Output is correct
7 Correct 550 ms 598008 KB Output is correct
8 Correct 579 ms 598032 KB Output is correct
9 Correct 552 ms 598176 KB Output is correct
10 Correct 567 ms 598124 KB Output is correct
11 Correct 588 ms 598116 KB Output is correct
12 Correct 545 ms 598100 KB Output is correct
13 Correct 544 ms 598008 KB Output is correct
14 Correct 551 ms 598008 KB Output is correct
15 Correct 547 ms 598020 KB Output is correct
16 Correct 544 ms 598008 KB Output is correct
17 Correct 550 ms 598320 KB Output is correct
18 Correct 544 ms 598324 KB Output is correct
19 Correct 547 ms 598264 KB Output is correct
20 Correct 563 ms 598392 KB Output is correct
21 Correct 559 ms 598292 KB Output is correct
22 Correct 545 ms 598392 KB Output is correct
23 Correct 549 ms 598380 KB Output is correct
24 Correct 581 ms 598136 KB Output is correct
25 Correct 563 ms 600136 KB Output is correct
26 Correct 557 ms 600300 KB Output is correct
27 Correct 565 ms 600416 KB Output is correct
28 Correct 556 ms 599020 KB Output is correct
29 Correct 580 ms 600168 KB Output is correct
30 Correct 586 ms 600172 KB Output is correct
31 Correct 570 ms 600152 KB Output is correct
32 Correct 571 ms 600156 KB Output is correct
33 Correct 678 ms 613396 KB Output is correct
34 Correct 698 ms 613488 KB Output is correct
35 Correct 689 ms 613488 KB Output is correct
36 Correct 669 ms 613488 KB Output is correct
37 Correct 803 ms 625112 KB Output is correct
38 Correct 789 ms 624936 KB Output is correct
39 Correct 791 ms 624868 KB Output is correct
40 Correct 772 ms 623124 KB Output is correct
41 Correct 660 ms 607632 KB Output is correct
42 Correct 688 ms 611052 KB Output is correct
43 Correct 830 ms 624372 KB Output is correct
44 Correct 835 ms 624720 KB Output is correct
45 Correct 691 ms 611692 KB Output is correct
46 Correct 685 ms 611136 KB Output is correct
47 Correct 821 ms 622744 KB Output is correct
48 Correct 899 ms 622900 KB Output is correct
49 Correct 552 ms 598524 KB Output is correct
50 Correct 548 ms 598448 KB Output is correct
51 Correct 547 ms 598116 KB Output is correct
52 Correct 549 ms 598100 KB Output is correct
53 Correct 553 ms 598264 KB Output is correct
54 Correct 571 ms 598392 KB Output is correct
55 Correct 546 ms 598456 KB Output is correct
56 Correct 549 ms 598404 KB Output is correct
57 Correct 547 ms 598416 KB Output is correct
58 Correct 558 ms 598264 KB Output is correct
59 Correct 546 ms 598428 KB Output is correct
60 Correct 559 ms 597980 KB Output is correct
61 Correct 1325 ms 650148 KB Output is correct
62 Correct 2199 ms 710096 KB Output is correct
63 Correct 2197 ms 710472 KB Output is correct
64 Correct 2210 ms 710576 KB Output is correct
65 Correct 760 ms 629248 KB Output is correct
66 Correct 973 ms 658424 KB Output is correct
67 Correct 1004 ms 661712 KB Output is correct
68 Correct 2267 ms 783772 KB Output is correct
69 Correct 2069 ms 783832 KB Output is correct
70 Correct 2787 ms 784072 KB Output is correct
71 Correct 2615 ms 784168 KB Output is correct
72 Correct 4006 ms 930640 KB Output is correct
73 Correct 3036 ms 793832 KB Output is correct
74 Correct 3143 ms 812260 KB Output is correct
75 Correct 4762 ms 924884 KB Output is correct
76 Correct 3122 ms 796176 KB Output is correct
77 Correct 3965 ms 865848 KB Output is correct
78 Correct 4955 ms 929044 KB Output is correct
79 Correct 2934 ms 782600 KB Output is correct
80 Correct 4789 ms 908656 KB Output is correct
81 Correct 4564 ms 899492 KB Output is correct
82 Correct 2582 ms 803384 KB Output is correct
83 Correct 3968 ms 930352 KB Output is correct
84 Correct 3968 ms 930596 KB Output is correct
85 Correct 3978 ms 930592 KB Output is correct
86 Correct 548 ms 597916 KB Output is correct
87 Correct 596 ms 598008 KB Output is correct
88 Correct 556 ms 598008 KB Output is correct
89 Correct 547 ms 597988 KB Output is correct
90 Correct 576 ms 598140 KB Output is correct