oj.uz

Submission #155795

# Submission time Handle Problem Language Result Execution time Memory
155795 2019-09-30T15:39:03 Z vanic Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 953696 KB 
#include "rect.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <stack>
#include <set>
#include <array>
 
using namespace std;
 
typedef long long ll;
const int maxn=2521;
 
int n, m;
int l[maxn][maxn];
//vector < int > r[maxn][maxn], c[maxn][maxn];
map < int, int > r[maxn][maxn], c[maxn][maxn];
int rind[maxn][maxn], cind[maxn][maxn];
pair < int, int > red[maxn][maxn], stup[maxn][maxn];
int bio2[maxn][maxn], bio3[maxn][maxn];
vector < array < int, 4 > > bio;

 
void upd1(int x){
	stack < pair < int, int > > q;
	q.push(make_pair(1e8, -1));
	for(int i=0; i<m; i++){
		while(q.top().first<=l[x][i]){
			q.pop();
		}
		red[x][i].first=q.top().second+1;
		q.push(make_pair(l[x][i], i));
	}
	while(!q.empty()){
		q.pop();
	}
	q.push(make_pair(1e8, m));
	for(int i=m-1; i>-1; i--){
		while(q.top().first<=l[x][i]){
			q.pop();
		}
		red[x][i].second=q.top().second-1;
		if(bio2[red[x][i].first][red[x][i].second]!=x+1){
			bio2[red[x][i].first][red[x][i].second]=x+1;
			r[red[x][i].first][red[x][i].second][x]=r[red[x][i].first][red[x][i].second][rind[red[x][i].first][red[x][i].second]]+1;
			rind[red[x][i].first][red[x][i].second]=x;
		}
		q.push(make_pair(l[x][i], i));
	}
}
 
void upd2(int x){
	stack < pair < int, int > > q;
	q.push(make_pair(1e8, -1));
	for(int i=0; i<n; i++){
		while(q.top().first<=l[i][x]){
			q.pop();
		}
		stup[i][x].first=q.top().second+1;
		q.push(make_pair(l[i][x], i));
	}
	while(!q.empty()){
		q.pop();
	}
	q.push(make_pair(1e8, n));
	for(int i=n-1; i>-1; i--){
		while(q.top().first<=l[i][x]){
			q.pop();
		}
		stup[i][x].second=q.top().second-1;
		if(bio3[stup[i][x].first][stup[i][x].second]!=x+1){
			bio3[stup[i][x].first][stup[i][x].second]=x+1;
			c[stup[i][x].first][stup[i][x].second][x]=c[stup[i][x].first][stup[i][x].second][cind[stup[i][x].first][stup[i][x].second]]+1;
			cind[stup[i][x].first][stup[i][x].second]=x;
		}
		q.push(make_pair(l[i][x], i));
	}
}
 
 
int binary(int x, vector < int > &l){
	int lo=0, hi=l.size(), mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		if(l[mid]<x){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
	}
	return lo;
}
 
void provjeri(int x, int y){
	int r1, r2, c1, c2;
	r1=red[x][y].first;
	r2=red[x][y].second;
	c1=stup[x][y].first;
	c2=stup[x][y].second;
	if(r1==0 || c1==0 || r2==m-1 || c2==n-1){
		return;
	}
//	int pos1=binary(c1, r[r1][r2]);
//	int pos2=binary(r1, c[c1][c2]);
	if(r[r1][r2][c2] && r[r1][r2][c1] && c[c1][c2][r2] && c[c1][c2][r1] && r[r1][r2][c2]-r[r1][r2][c1]==c2-c1 && c[c1][c2][r2]-c[c1][c2][r1]==r2-r1){
		bio.push_back({r1, r2, c1, c2});
	}
}
 
long long count_rectangles(vector < vector < int > > a){
	n=a.size();
	m=a[0].size();
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			l[i][j]=a[i][j];
		}
	}
	for(int i=0; i<n; i++){
		upd1(i);
	}
	for(int i=0; i<m; i++){
		upd2(i);
	}
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			provjeri(i, j);
		}
	}
	sort(bio.begin(), bio.end());
	bio.erase(unique(bio.begin(), bio.end()), bio.end());
	return bio.size();
}
 
/*
int main(){
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%d", &l[i][j]);
		}
	}
	for(int i=0; i<n; i++){
		upd1(i);
	}
	for(int i=0; i<m; i++){
		upd2(i);
	}
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			provjeri(i, j);
		}
	}
	sort(bio.begin(), bio.end());
	bio.erase(unique(bio.begin(), bio.end()), bio.end());
	printf("%d\n", bio.size());
	return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 597576 KB Output is correct
2 Correct 651 ms 598344 KB Output is correct
3 Correct 602 ms 598340 KB Output is correct
4 Correct 550 ms 598264 KB Output is correct
5 Correct 582 ms 597780 KB Output is correct
6 Correct 589 ms 598400 KB Output is correct
7 Correct 568 ms 598104 KB Output is correct
8 Correct 557 ms 597904 KB Output is correct
9 Correct 539 ms 598392 KB Output is correct
10 Correct 543 ms 598236 KB Output is correct
11 Correct 541 ms 598268 KB Output is correct
12 Correct 540 ms 598356 KB Output is correct
13 Correct 544 ms 597356 KB Output is correct
14 Correct 544 ms 597508 KB Output is correct
15 Correct 600 ms 597604 KB Output is correct
16 Correct 579 ms 597412 KB Output is correct
17 Correct 536 ms 597456 KB Output is correct
18 Correct 543 ms 597368 KB Output is correct
19 Correct 544 ms 598276 KB Output is correct
20 Correct 534 ms 597752 KB Output is correct
21 Correct 537 ms 597544 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 597576 KB Output is correct
2 Correct 651 ms 598344 KB Output is correct
3 Correct 602 ms 598340 KB Output is correct
4 Correct 550 ms 598264 KB Output is correct
5 Correct 582 ms 597780 KB Output is correct
6 Correct 589 ms 598400 KB Output is correct
7 Correct 568 ms 598104 KB Output is correct
8 Correct 557 ms 597904 KB Output is correct
9 Correct 539 ms 598392 KB Output is correct
10 Correct 543 ms 598236 KB Output is correct
11 Correct 541 ms 598268 KB Output is correct
12 Correct 540 ms 598356 KB Output is correct
13 Correct 544 ms 597356 KB Output is correct
14 Correct 544 ms 597508 KB Output is correct
15 Correct 600 ms 597604 KB Output is correct
16 Correct 579 ms 597412 KB Output is correct
17 Correct 545 ms 600596 KB Output is correct
18 Correct 546 ms 600820 KB Output is correct
19 Correct 550 ms 600592 KB Output is correct
20 Correct 551 ms 600312 KB Output is correct
21 Correct 558 ms 600752 KB Output is correct
22 Correct 547 ms 600580 KB Output is correct
23 Correct 546 ms 600640 KB Output is correct
24 Correct 543 ms 599804 KB Output is correct
25 Correct 536 ms 597456 KB Output is correct
26 Correct 543 ms 597368 KB Output is correct
27 Correct 544 ms 598276 KB Output is correct
28 Correct 534 ms 597752 KB Output is correct
29 Correct 537 ms 597544 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 597576 KB Output is correct
2 Correct 651 ms 598344 KB Output is correct
3 Correct 602 ms 598340 KB Output is correct
4 Correct 550 ms 598264 KB Output is correct
5 Correct 582 ms 597780 KB Output is correct
6 Correct 589 ms 598400 KB Output is correct
7 Correct 568 ms 598104 KB Output is correct
8 Correct 557 ms 597904 KB Output is correct
9 Correct 539 ms 598392 KB Output is correct
10 Correct 543 ms 598236 KB Output is correct
11 Correct 541 ms 598268 KB Output is correct
12 Correct 540 ms 598356 KB Output is correct
13 Correct 544 ms 597356 KB Output is correct
14 Correct 544 ms 597508 KB Output is correct
15 Correct 600 ms 597604 KB Output is correct
16 Correct 579 ms 597412 KB Output is correct
17 Correct 545 ms 600596 KB Output is correct
18 Correct 546 ms 600820 KB Output is correct
19 Correct 550 ms 600592 KB Output is correct
20 Correct 551 ms 600312 KB Output is correct
21 Correct 558 ms 600752 KB Output is correct
22 Correct 547 ms 600580 KB Output is correct
23 Correct 546 ms 600640 KB Output is correct
24 Correct 543 ms 599804 KB Output is correct
25 Correct 588 ms 609236 KB Output is correct
26 Correct 592 ms 609492 KB Output is correct
27 Correct 609 ms 609272 KB Output is correct
28 Correct 570 ms 606708 KB Output is correct
29 Correct 605 ms 610036 KB Output is correct
30 Correct 602 ms 610080 KB Output is correct
31 Correct 599 ms 609520 KB Output is correct
32 Correct 598 ms 609396 KB Output is correct
33 Correct 536 ms 597456 KB Output is correct
34 Correct 543 ms 597368 KB Output is correct
35 Correct 544 ms 598276 KB Output is correct
36 Correct 534 ms 597752 KB Output is correct
37 Correct 537 ms 597544 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 597576 KB Output is correct
2 Correct 651 ms 598344 KB Output is correct
3 Correct 602 ms 598340 KB Output is correct
4 Correct 550 ms 598264 KB Output is correct
5 Correct 582 ms 597780 KB Output is correct
6 Correct 589 ms 598400 KB Output is correct
7 Correct 568 ms 598104 KB Output is correct
8 Correct 557 ms 597904 KB Output is correct
9 Correct 539 ms 598392 KB Output is correct
10 Correct 543 ms 598236 KB Output is correct
11 Correct 541 ms 598268 KB Output is correct
12 Correct 540 ms 598356 KB Output is correct
13 Correct 544 ms 597356 KB Output is correct
14 Correct 544 ms 597508 KB Output is correct
15 Correct 600 ms 597604 KB Output is correct
16 Correct 579 ms 597412 KB Output is correct
17 Correct 545 ms 600596 KB Output is correct
18 Correct 546 ms 600820 KB Output is correct
19 Correct 550 ms 600592 KB Output is correct
20 Correct 551 ms 600312 KB Output is correct
21 Correct 558 ms 600752 KB Output is correct
22 Correct 547 ms 600580 KB Output is correct
23 Correct 546 ms 600640 KB Output is correct
24 Correct 543 ms 599804 KB Output is correct
25 Correct 588 ms 609236 KB Output is correct
26 Correct 592 ms 609492 KB Output is correct
27 Correct 609 ms 609272 KB Output is correct
28 Correct 570 ms 606708 KB Output is correct
29 Correct 605 ms 610036 KB Output is correct
30 Correct 602 ms 610080 KB Output is correct
31 Correct 599 ms 609520 KB Output is correct
32 Correct 598 ms 609396 KB Output is correct
33 Correct 968 ms 706716 KB Output is correct
34 Correct 1045 ms 706636 KB Output is correct
35 Correct 1071 ms 706676 KB Output is correct
36 Correct 1129 ms 706632 KB Output is correct
37 Correct 1460 ms 688240 KB Output is correct
38 Correct 1469 ms 688208 KB Output is correct
39 Correct 1549 ms 688540 KB Output is correct
40 Correct 1408 ms 683824 KB Output is correct
41 Correct 911 ms 651888 KB Output is correct
42 Correct 1022 ms 661156 KB Output is correct
43 Correct 1811 ms 700304 KB Output is correct
44 Correct 1660 ms 703616 KB Output is correct
45 Correct 1053 ms 657852 KB Output is correct
46 Correct 1340 ms 653592 KB Output is correct
47 Correct 1749 ms 691044 KB Output is correct
48 Correct 1650 ms 692512 KB Output is correct
49 Correct 536 ms 597456 KB Output is correct
50 Correct 543 ms 597368 KB Output is correct
51 Correct 544 ms 598276 KB Output is correct
52 Correct 534 ms 597752 KB Output is correct
53 Correct 537 ms 597544 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 618548 KB Output is correct
2 Correct 569 ms 615252 KB Output is correct
3 Correct 542 ms 597800 KB Output is correct
4 Correct 542 ms 597368 KB Output is correct
5 Correct 565 ms 616516 KB Output is correct
6 Correct 565 ms 616300 KB Output is correct
7 Correct 565 ms 616440 KB Output is correct
8 Correct 572 ms 615032 KB Output is correct
9 Correct 609 ms 614904 KB Output is correct
10 Correct 702 ms 607992 KB Output is correct
11 Correct 598 ms 613412 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 597716 KB Output is correct
2 Correct 3293 ms 826636 KB Output is correct
3 Execution timed out 5113 ms 953696 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 597576 KB Output is correct
2 Correct 651 ms 598344 KB Output is correct
3 Correct 602 ms 598340 KB Output is correct
4 Correct 550 ms 598264 KB Output is correct
5 Correct 582 ms 597780 KB Output is correct
6 Correct 589 ms 598400 KB Output is correct
7 Correct 568 ms 598104 KB Output is correct
8 Correct 557 ms 597904 KB Output is correct
9 Correct 539 ms 598392 KB Output is correct
10 Correct 543 ms 598236 KB Output is correct
11 Correct 541 ms 598268 KB Output is correct
12 Correct 540 ms 598356 KB Output is correct
13 Correct 544 ms 597356 KB Output is correct
14 Correct 544 ms 597508 KB Output is correct
15 Correct 600 ms 597604 KB Output is correct
16 Correct 579 ms 597412 KB Output is correct
17 Correct 545 ms 600596 KB Output is correct
18 Correct 546 ms 600820 KB Output is correct
19 Correct 550 ms 600592 KB Output is correct
20 Correct 551 ms 600312 KB Output is correct
21 Correct 558 ms 600752 KB Output is correct
22 Correct 547 ms 600580 KB Output is correct
23 Correct 546 ms 600640 KB Output is correct
24 Correct 543 ms 599804 KB Output is correct
25 Correct 588 ms 609236 KB Output is correct
26 Correct 592 ms 609492 KB Output is correct
27 Correct 609 ms 609272 KB Output is correct
28 Correct 570 ms 606708 KB Output is correct
29 Correct 605 ms 610036 KB Output is correct
30 Correct 602 ms 610080 KB Output is correct
31 Correct 599 ms 609520 KB Output is correct
32 Correct 598 ms 609396 KB Output is correct
33 Correct 968 ms 706716 KB Output is correct
34 Correct 1045 ms 706636 KB Output is correct
35 Correct 1071 ms 706676 KB Output is correct
36 Correct 1129 ms 706632 KB Output is correct
37 Correct 1460 ms 688240 KB Output is correct
38 Correct 1469 ms 688208 KB Output is correct
39 Correct 1549 ms 688540 KB Output is correct
40 Correct 1408 ms 683824 KB Output is correct
41 Correct 911 ms 651888 KB Output is correct
42 Correct 1022 ms 661156 KB Output is correct
43 Correct 1811 ms 700304 KB Output is correct
44 Correct 1660 ms 703616 KB Output is correct
45 Correct 1053 ms 657852 KB Output is correct
46 Correct 1340 ms 653592 KB Output is correct
47 Correct 1749 ms 691044 KB Output is correct
48 Correct 1650 ms 692512 KB Output is correct
49 Correct 622 ms 618548 KB Output is correct
50 Correct 569 ms 615252 KB Output is correct
51 Correct 542 ms 597800 KB Output is correct
52 Correct 542 ms 597368 KB Output is correct
53 Correct 565 ms 616516 KB Output is correct
54 Correct 565 ms 616300 KB Output is correct
55 Correct 565 ms 616440 KB Output is correct
56 Correct 572 ms 615032 KB Output is correct
57 Correct 609 ms 614904 KB Output is correct
58 Correct 702 ms 607992 KB Output is correct
59 Correct 598 ms 613412 KB Output is correct
60 Correct 547 ms 597716 KB Output is correct
61 Correct 3293 ms 826636 KB Output is correct
62 Execution timed out 5113 ms 953696 KB Time limit exceeded
63 Halted 0 ms 0 KB -