oj.uz

Submission #155599

# Submission time Handle Problem Language Result Execution time Memory
155599 2019-09-29T08:01:00 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 2604 ms 523540 KB 
#include "rect.h"
#include <cstdio>
#include <vector>	
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>

using namespace std;

typedef long long ll;
const int maxn=2505;

int n, m;
int l[maxn][maxn];
vector < int > r[maxn][maxn], c[maxn][maxn];
pair < int, int > red[maxn][maxn], stup[maxn][maxn];
int bio2[maxn][maxn], bio3[maxn][maxn];
map < ll, bool > bio;

ll hashiraj(ll a, ll b, ll c, ll d){
	return a*maxn*maxn*maxn+b*maxn*maxn+c*maxn+d;
}

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].push_back(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].push_back(x);
		}
		q.push(make_pair(l[i][x], i));
	}
}


int binary(int x, bool p, int y, int z){
	int lo=0, hi, mid;
	if(p){
		hi=r[y][z].size()-1;
	}
	else{
		hi=c[y][z].size()-1;
	}
	while(lo<hi){
		mid=(lo+hi)/2;
		if(p){
			if(r[y][z][mid]<x){
				lo=mid+1;
			}
			else{
				hi=mid;
			}
		}
		else{
			if(c[y][z][mid]<x){
				lo=mid+1;
			}
			else{
				hi=mid;
			}
		}
	}
	return lo;
}

bool 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 0;
	}
	int pos1=binary(c1, 1, r1, r2);
	int pos2=binary(r1, 0, c1, c2);
/*	printf("novi\n");
	printf("%d %d\n", x, y);
	printf("%d %d\n", r1, r2);
	printf("%d %d\n", c1, c2);
	printf("%d %d\n", pos1, pos2);
	for(int i=0; i<r[r1][r2].size(); i++){
		printf("%d ", r[r1][r2][i]);
	}
	printf("\n");
	for(int i=0; i<c[c1][c2].size(); i++){
		printf("%d ", c[c1][c2][i]);
	}
	printf("\n");*/
	if(r[r1][r2][pos1]==c1 && r[r1][r2].size()-pos1-c2+c1-1>=0 && r[r1][r2][pos1+c2-c1]==c2
	&& c[c1][c2][pos2]==r1 && c[c1][c2].size()-pos2-r2+r1-1>=0 && c[c1][c2][pos2+r2-r1]==r2){
		if(!bio[hashiraj(r1, r2, c1, c2)]){
//			printf("cudo\n");
			bio[hashiraj(r1, r2, c1, c2)]=1;
			return 1;
		}
	}
	return 0;
}

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);
	}
	int br=0;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			if(provjeri(i, j)){
				br++;
			}
		}
	}
	return br;
}

/*
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);
	}
	int br=0;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			if(provjeri(i, j)){
				br++;
			}
		}
	}
	printf("%d\n", br);
	return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295164 KB Output is correct
2 Correct 380 ms 295800 KB Output is correct
3 Correct 284 ms 295656 KB Output is correct
4 Correct 269 ms 295772 KB Output is correct
5 Correct 271 ms 295544 KB Output is correct
6 Correct 273 ms 295692 KB Output is correct
7 Correct 270 ms 295672 KB Output is correct
8 Correct 275 ms 295452 KB Output is correct
9 Correct 286 ms 295664 KB Output is correct
10 Correct 270 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 279 ms 295664 KB Output is correct
13 Correct 294 ms 295144 KB Output is correct
14 Correct 270 ms 295160 KB Output is correct
15 Correct 270 ms 295236 KB Output is correct
16 Correct 269 ms 295292 KB Output is correct
17 Correct 270 ms 295024 KB Output is correct
18 Correct 269 ms 295028 KB Output is correct
19 Correct 270 ms 295736 KB Output is correct
20 Correct 269 ms 295564 KB Output is correct
21 Correct 268 ms 295288 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295164 KB Output is correct
2 Correct 380 ms 295800 KB Output is correct
3 Correct 284 ms 295656 KB Output is correct
4 Correct 269 ms 295772 KB Output is correct
5 Correct 271 ms 295544 KB Output is correct
6 Correct 273 ms 295692 KB Output is correct
7 Correct 270 ms 295672 KB Output is correct
8 Correct 275 ms 295452 KB Output is correct
9 Correct 286 ms 295664 KB Output is correct
10 Correct 270 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 279 ms 295664 KB Output is correct
13 Correct 294 ms 295144 KB Output is correct
14 Correct 270 ms 295160 KB Output is correct
15 Correct 270 ms 295236 KB Output is correct
16 Correct 269 ms 295292 KB Output is correct
17 Correct 280 ms 297272 KB Output is correct
18 Correct 286 ms 297276 KB Output is correct
19 Correct 271 ms 297312 KB Output is correct
20 Correct 297 ms 296952 KB Output is correct
21 Correct 272 ms 297000 KB Output is correct
22 Correct 279 ms 297080 KB Output is correct
23 Correct 272 ms 297080 KB Output is correct
24 Incorrect 270 ms 296656 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295164 KB Output is correct
2 Correct 380 ms 295800 KB Output is correct
3 Correct 284 ms 295656 KB Output is correct
4 Correct 269 ms 295772 KB Output is correct
5 Correct 271 ms 295544 KB Output is correct
6 Correct 273 ms 295692 KB Output is correct
7 Correct 270 ms 295672 KB Output is correct
8 Correct 275 ms 295452 KB Output is correct
9 Correct 286 ms 295664 KB Output is correct
10 Correct 270 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 279 ms 295664 KB Output is correct
13 Correct 294 ms 295144 KB Output is correct
14 Correct 270 ms 295160 KB Output is correct
15 Correct 270 ms 295236 KB Output is correct
16 Correct 269 ms 295292 KB Output is correct
17 Correct 280 ms 297272 KB Output is correct
18 Correct 286 ms 297276 KB Output is correct
19 Correct 271 ms 297312 KB Output is correct
20 Correct 297 ms 296952 KB Output is correct
21 Correct 272 ms 297000 KB Output is correct
22 Correct 279 ms 297080 KB Output is correct
23 Correct 272 ms 297080 KB Output is correct
24 Incorrect 270 ms 296656 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295164 KB Output is correct
2 Correct 380 ms 295800 KB Output is correct
3 Correct 284 ms 295656 KB Output is correct
4 Correct 269 ms 295772 KB Output is correct
5 Correct 271 ms 295544 KB Output is correct
6 Correct 273 ms 295692 KB Output is correct
7 Correct 270 ms 295672 KB Output is correct
8 Correct 275 ms 295452 KB Output is correct
9 Correct 286 ms 295664 KB Output is correct
10 Correct 270 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 279 ms 295664 KB Output is correct
13 Correct 294 ms 295144 KB Output is correct
14 Correct 270 ms 295160 KB Output is correct
15 Correct 270 ms 295236 KB Output is correct
16 Correct 269 ms 295292 KB Output is correct
17 Correct 280 ms 297272 KB Output is correct
18 Correct 286 ms 297276 KB Output is correct
19 Correct 271 ms 297312 KB Output is correct
20 Correct 297 ms 296952 KB Output is correct
21 Correct 272 ms 297000 KB Output is correct
22 Correct 279 ms 297080 KB Output is correct
23 Correct 272 ms 297080 KB Output is correct
24 Incorrect 270 ms 296656 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 305608 KB Output is correct
2 Correct 287 ms 304016 KB Output is correct
3 Correct 272 ms 295288 KB Output is correct
4 Correct 269 ms 295092 KB Output is correct
5 Correct 282 ms 304504 KB Output is correct
6 Correct 281 ms 304504 KB Output is correct
7 Correct 284 ms 304504 KB Output is correct
8 Correct 281 ms 303864 KB Output is correct
9 Correct 284 ms 303752 KB Output is correct
10 Correct 314 ms 300576 KB Output is correct
11 Correct 325 ms 303076 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 295268 KB Output is correct
2 Correct 1238 ms 409768 KB Output is correct
3 Correct 2463 ms 522584 KB Output is correct
4 Correct 2604 ms 523428 KB Output is correct
5 Correct 2565 ms 523540 KB Output is correct
6 Correct 576 ms 379948 KB Output is correct
7 Correct 928 ms 463804 KB Output is correct
8 Correct 972 ms 466968 KB Output is correct
9 Correct 270 ms 295024 KB Output is correct
10 Correct 269 ms 295028 KB Output is correct
11 Correct 270 ms 295736 KB Output is correct
12 Correct 269 ms 295564 KB Output is correct
13 Correct 268 ms 295288 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295164 KB Output is correct
2 Correct 380 ms 295800 KB Output is correct
3 Correct 284 ms 295656 KB Output is correct
4 Correct 269 ms 295772 KB Output is correct
5 Correct 271 ms 295544 KB Output is correct
6 Correct 273 ms 295692 KB Output is correct
7 Correct 270 ms 295672 KB Output is correct
8 Correct 275 ms 295452 KB Output is correct
9 Correct 286 ms 295664 KB Output is correct
10 Correct 270 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 279 ms 295664 KB Output is correct
13 Correct 294 ms 295144 KB Output is correct
14 Correct 270 ms 295160 KB Output is correct
15 Correct 270 ms 295236 KB Output is correct
16 Correct 269 ms 295292 KB Output is correct
17 Correct 280 ms 297272 KB Output is correct
18 Correct 286 ms 297276 KB Output is correct
19 Correct 271 ms 297312 KB Output is correct
20 Correct 297 ms 296952 KB Output is correct
21 Correct 272 ms 297000 KB Output is correct
22 Correct 279 ms 297080 KB Output is correct
23 Correct 272 ms 297080 KB Output is correct
24 Incorrect 270 ms 296656 KB Output isn't correct