oj.uz

Submission #155802

# Submission time Handle Problem Language Result Execution time Memory
155802 2019-09-30T15:46:33 Z vanic Rectangles (IOI19_rect) C++14
59 / 100
 4988 ms 1048580 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];
unordered_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].find(c2)!=r[r1][r2].end() && r[r1][r2].find(c1)!=r[r1][r2].end()
	&& c[c1][c2].find(r2)!=c[c1][c2].end() && c[c1][c2].find(r1)!=c[c1][c2].end()
	&& 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 704 ms 697028 KB Output is correct
2 Correct 736 ms 697976 KB Output is correct
3 Correct 725 ms 697864 KB Output is correct
4 Correct 691 ms 697736 KB Output is correct
5 Correct 757 ms 697248 KB Output is correct
6 Correct 689 ms 697896 KB Output is correct
7 Correct 698 ms 697700 KB Output is correct
8 Correct 717 ms 697528 KB Output is correct
9 Correct 692 ms 697848 KB Output is correct
10 Correct 695 ms 697812 KB Output is correct
11 Correct 698 ms 697848 KB Output is correct
12 Correct 708 ms 697724 KB Output is correct
13 Correct 703 ms 696824 KB Output is correct
14 Correct 691 ms 697092 KB Output is correct
15 Correct 728 ms 696976 KB Output is correct
16 Correct 703 ms 696920 KB Output is correct
17 Correct 691 ms 696824 KB Output is correct
18 Correct 687 ms 696848 KB Output is correct
19 Correct 696 ms 697720 KB Output is correct
20 Correct 685 ms 697280 KB Output is correct
21 Correct 688 ms 697000 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 697028 KB Output is correct
2 Correct 736 ms 697976 KB Output is correct
3 Correct 725 ms 697864 KB Output is correct
4 Correct 691 ms 697736 KB Output is correct
5 Correct 757 ms 697248 KB Output is correct
6 Correct 689 ms 697896 KB Output is correct
7 Correct 698 ms 697700 KB Output is correct
8 Correct 717 ms 697528 KB Output is correct
9 Correct 692 ms 697848 KB Output is correct
10 Correct 695 ms 697812 KB Output is correct
11 Correct 698 ms 697848 KB Output is correct
12 Correct 708 ms 697724 KB Output is correct
13 Correct 703 ms 696824 KB Output is correct
14 Correct 691 ms 697092 KB Output is correct
15 Correct 728 ms 696976 KB Output is correct
16 Correct 703 ms 696920 KB Output is correct
17 Correct 700 ms 700188 KB Output is correct
18 Correct 700 ms 700152 KB Output is correct
19 Correct 698 ms 700152 KB Output is correct
20 Correct 695 ms 699612 KB Output is correct
21 Correct 702 ms 700152 KB Output is correct
22 Correct 705 ms 700024 KB Output is correct
23 Correct 708 ms 700252 KB Output is correct
24 Correct 702 ms 699164 KB Output is correct
25 Correct 691 ms 696824 KB Output is correct
26 Correct 687 ms 696848 KB Output is correct
27 Correct 696 ms 697720 KB Output is correct
28 Correct 685 ms 697280 KB Output is correct
29 Correct 688 ms 697000 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 697028 KB Output is correct
2 Correct 736 ms 697976 KB Output is correct
3 Correct 725 ms 697864 KB Output is correct
4 Correct 691 ms 697736 KB Output is correct
5 Correct 757 ms 697248 KB Output is correct
6 Correct 689 ms 697896 KB Output is correct
7 Correct 698 ms 697700 KB Output is correct
8 Correct 717 ms 697528 KB Output is correct
9 Correct 692 ms 697848 KB Output is correct
10 Correct 695 ms 697812 KB Output is correct
11 Correct 698 ms 697848 KB Output is correct
12 Correct 708 ms 697724 KB Output is correct
13 Correct 703 ms 696824 KB Output is correct
14 Correct 691 ms 697092 KB Output is correct
15 Correct 728 ms 696976 KB Output is correct
16 Correct 703 ms 696920 KB Output is correct
17 Correct 700 ms 700188 KB Output is correct
18 Correct 700 ms 700152 KB Output is correct
19 Correct 698 ms 700152 KB Output is correct
20 Correct 695 ms 699612 KB Output is correct
21 Correct 702 ms 700152 KB Output is correct
22 Correct 705 ms 700024 KB Output is correct
23 Correct 708 ms 700252 KB Output is correct
24 Correct 702 ms 699164 KB Output is correct
25 Correct 743 ms 708372 KB Output is correct
26 Correct 735 ms 708340 KB Output is correct
27 Correct 745 ms 708556 KB Output is correct
28 Correct 731 ms 705436 KB Output is correct
29 Correct 800 ms 708216 KB Output is correct
30 Correct 762 ms 708396 KB Output is correct
31 Correct 746 ms 707992 KB Output is correct
32 Correct 750 ms 707844 KB Output is correct
33 Correct 691 ms 696824 KB Output is correct
34 Correct 687 ms 696848 KB Output is correct
35 Correct 696 ms 697720 KB Output is correct
36 Correct 685 ms 697280 KB Output is correct
37 Correct 688 ms 697000 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 697028 KB Output is correct
2 Correct 736 ms 697976 KB Output is correct
3 Correct 725 ms 697864 KB Output is correct
4 Correct 691 ms 697736 KB Output is correct
5 Correct 757 ms 697248 KB Output is correct
6 Correct 689 ms 697896 KB Output is correct
7 Correct 698 ms 697700 KB Output is correct
8 Correct 717 ms 697528 KB Output is correct
9 Correct 692 ms 697848 KB Output is correct
10 Correct 695 ms 697812 KB Output is correct
11 Correct 698 ms 697848 KB Output is correct
12 Correct 708 ms 697724 KB Output is correct
13 Correct 703 ms 696824 KB Output is correct
14 Correct 691 ms 697092 KB Output is correct
15 Correct 728 ms 696976 KB Output is correct
16 Correct 703 ms 696920 KB Output is correct
17 Correct 700 ms 700188 KB Output is correct
18 Correct 700 ms 700152 KB Output is correct
19 Correct 698 ms 700152 KB Output is correct
20 Correct 695 ms 699612 KB Output is correct
21 Correct 702 ms 700152 KB Output is correct
22 Correct 705 ms 700024 KB Output is correct
23 Correct 708 ms 700252 KB Output is correct
24 Correct 702 ms 699164 KB Output is correct
25 Correct 743 ms 708372 KB Output is correct
26 Correct 735 ms 708340 KB Output is correct
27 Correct 745 ms 708556 KB Output is correct
28 Correct 731 ms 705436 KB Output is correct
29 Correct 800 ms 708216 KB Output is correct
30 Correct 762 ms 708396 KB Output is correct
31 Correct 746 ms 707992 KB Output is correct
32 Correct 750 ms 707844 KB Output is correct
33 Correct 1328 ms 800652 KB Output is correct
34 Correct 1229 ms 800664 KB Output is correct
35 Correct 1194 ms 800652 KB Output is correct
36 Correct 1286 ms 800680 KB Output is correct
37 Correct 1447 ms 777028 KB Output is correct
38 Correct 1403 ms 776928 KB Output is correct
39 Correct 1386 ms 776988 KB Output is correct
40 Correct 1305 ms 772836 KB Output is correct
41 Correct 969 ms 742396 KB Output is correct
42 Correct 1105 ms 748508 KB Output is correct
43 Correct 1596 ms 783308 KB Output is correct
44 Correct 1611 ms 784600 KB Output is correct
45 Correct 1132 ms 748344 KB Output is correct
46 Correct 1287 ms 744176 KB Output is correct
47 Correct 1632 ms 776148 KB Output is correct
48 Correct 1537 ms 776520 KB Output is correct
49 Correct 691 ms 696824 KB Output is correct
50 Correct 687 ms 696848 KB Output is correct
51 Correct 696 ms 697720 KB Output is correct
52 Correct 685 ms 697280 KB Output is correct
53 Correct 688 ms 697000 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 718052 KB Output is correct
2 Correct 759 ms 714872 KB Output is correct
3 Correct 694 ms 697208 KB Output is correct
4 Correct 693 ms 696952 KB Output is correct
5 Correct 719 ms 716100 KB Output is correct
6 Correct 738 ms 715844 KB Output is correct
7 Correct 729 ms 716084 KB Output is correct
8 Correct 722 ms 714680 KB Output is correct
9 Correct 722 ms 714268 KB Output is correct
10 Correct 711 ms 707528 KB Output is correct
11 Correct 720 ms 712956 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 697160 KB Output is correct
2 Correct 2904 ms 875500 KB Output is correct
3 Runtime error 4988 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 697028 KB Output is correct
2 Correct 736 ms 697976 KB Output is correct
3 Correct 725 ms 697864 KB Output is correct
4 Correct 691 ms 697736 KB Output is correct
5 Correct 757 ms 697248 KB Output is correct
6 Correct 689 ms 697896 KB Output is correct
7 Correct 698 ms 697700 KB Output is correct
8 Correct 717 ms 697528 KB Output is correct
9 Correct 692 ms 697848 KB Output is correct
10 Correct 695 ms 697812 KB Output is correct
11 Correct 698 ms 697848 KB Output is correct
12 Correct 708 ms 697724 KB Output is correct
13 Correct 703 ms 696824 KB Output is correct
14 Correct 691 ms 697092 KB Output is correct
15 Correct 728 ms 696976 KB Output is correct
16 Correct 703 ms 696920 KB Output is correct
17 Correct 700 ms 700188 KB Output is correct
18 Correct 700 ms 700152 KB Output is correct
19 Correct 698 ms 700152 KB Output is correct
20 Correct 695 ms 699612 KB Output is correct
21 Correct 702 ms 700152 KB Output is correct
22 Correct 705 ms 700024 KB Output is correct
23 Correct 708 ms 700252 KB Output is correct
24 Correct 702 ms 699164 KB Output is correct
25 Correct 743 ms 708372 KB Output is correct
26 Correct 735 ms 708340 KB Output is correct
27 Correct 745 ms 708556 KB Output is correct
28 Correct 731 ms 705436 KB Output is correct
29 Correct 800 ms 708216 KB Output is correct
30 Correct 762 ms 708396 KB Output is correct
31 Correct 746 ms 707992 KB Output is correct
32 Correct 750 ms 707844 KB Output is correct
33 Correct 1328 ms 800652 KB Output is correct
34 Correct 1229 ms 800664 KB Output is correct
35 Correct 1194 ms 800652 KB Output is correct
36 Correct 1286 ms 800680 KB Output is correct
37 Correct 1447 ms 777028 KB Output is correct
38 Correct 1403 ms 776928 KB Output is correct
39 Correct 1386 ms 776988 KB Output is correct
40 Correct 1305 ms 772836 KB Output is correct
41 Correct 969 ms 742396 KB Output is correct
42 Correct 1105 ms 748508 KB Output is correct
43 Correct 1596 ms 783308 KB Output is correct
44 Correct 1611 ms 784600 KB Output is correct
45 Correct 1132 ms 748344 KB Output is correct
46 Correct 1287 ms 744176 KB Output is correct
47 Correct 1632 ms 776148 KB Output is correct
48 Correct 1537 ms 776520 KB Output is correct
49 Correct 727 ms 718052 KB Output is correct
50 Correct 759 ms 714872 KB Output is correct
51 Correct 694 ms 697208 KB Output is correct
52 Correct 693 ms 696952 KB Output is correct
53 Correct 719 ms 716100 KB Output is correct
54 Correct 738 ms 715844 KB Output is correct
55 Correct 729 ms 716084 KB Output is correct
56 Correct 722 ms 714680 KB Output is correct
57 Correct 722 ms 714268 KB Output is correct
58 Correct 711 ms 707528 KB Output is correct
59 Correct 720 ms 712956 KB Output is correct
60 Correct 705 ms 697160 KB Output is correct
61 Correct 2904 ms 875500 KB Output is correct
62 Runtime error 4988 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Halted 0 ms 0 KB -