oj.uz

Submission #155597

# Submission time Handle Problem Language Result Execution time Memory
155597 2019-09-29T07:53:54 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 2545 ms 523552 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;

inline 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, vector < int > &l){
	int lo=0, hi=l.size()-1, mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		if(l[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, r[r1][r2]);
	int pos2=binary(r1, c[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 281 ms 295160 KB Output is correct
2 Correct 299 ms 295736 KB Output is correct
3 Correct 310 ms 295972 KB Output is correct
4 Correct 273 ms 295800 KB Output is correct
5 Correct 283 ms 295444 KB Output is correct
6 Correct 271 ms 295800 KB Output is correct
7 Correct 269 ms 295672 KB Output is correct
8 Correct 276 ms 295428 KB Output is correct
9 Correct 288 ms 295628 KB Output is correct
10 Correct 283 ms 295672 KB Output is correct
11 Correct 282 ms 295928 KB Output is correct
12 Correct 271 ms 295668 KB Output is correct
13 Correct 267 ms 295032 KB Output is correct
14 Correct 275 ms 295228 KB Output is correct
15 Correct 272 ms 295196 KB Output is correct
16 Correct 266 ms 295160 KB Output is correct
17 Correct 270 ms 295040 KB Output is correct
18 Correct 269 ms 295092 KB Output is correct
19 Correct 313 ms 295620 KB Output is correct
20 Correct 269 ms 295544 KB Output is correct
21 Correct 271 ms 295160 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 295160 KB Output is correct
2 Correct 299 ms 295736 KB Output is correct
3 Correct 310 ms 295972 KB Output is correct
4 Correct 273 ms 295800 KB Output is correct
5 Correct 283 ms 295444 KB Output is correct
6 Correct 271 ms 295800 KB Output is correct
7 Correct 269 ms 295672 KB Output is correct
8 Correct 276 ms 295428 KB Output is correct
9 Correct 288 ms 295628 KB Output is correct
10 Correct 283 ms 295672 KB Output is correct
11 Correct 282 ms 295928 KB Output is correct
12 Correct 271 ms 295668 KB Output is correct
13 Correct 267 ms 295032 KB Output is correct
14 Correct 275 ms 295228 KB Output is correct
15 Correct 272 ms 295196 KB Output is correct
16 Correct 266 ms 295160 KB Output is correct
17 Correct 274 ms 297248 KB Output is correct
18 Correct 274 ms 297416 KB Output is correct
19 Correct 276 ms 297228 KB Output is correct
20 Correct 271 ms 296952 KB Output is correct
21 Correct 280 ms 297084 KB Output is correct
22 Correct 272 ms 297180 KB Output is correct
23 Correct 275 ms 297080 KB Output is correct
24 Incorrect 290 ms 296728 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 295160 KB Output is correct
2 Correct 299 ms 295736 KB Output is correct
3 Correct 310 ms 295972 KB Output is correct
4 Correct 273 ms 295800 KB Output is correct
5 Correct 283 ms 295444 KB Output is correct
6 Correct 271 ms 295800 KB Output is correct
7 Correct 269 ms 295672 KB Output is correct
8 Correct 276 ms 295428 KB Output is correct
9 Correct 288 ms 295628 KB Output is correct
10 Correct 283 ms 295672 KB Output is correct
11 Correct 282 ms 295928 KB Output is correct
12 Correct 271 ms 295668 KB Output is correct
13 Correct 267 ms 295032 KB Output is correct
14 Correct 275 ms 295228 KB Output is correct
15 Correct 272 ms 295196 KB Output is correct
16 Correct 266 ms 295160 KB Output is correct
17 Correct 274 ms 297248 KB Output is correct
18 Correct 274 ms 297416 KB Output is correct
19 Correct 276 ms 297228 KB Output is correct
20 Correct 271 ms 296952 KB Output is correct
21 Correct 280 ms 297084 KB Output is correct
22 Correct 272 ms 297180 KB Output is correct
23 Correct 275 ms 297080 KB Output is correct
24 Incorrect 290 ms 296728 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 295160 KB Output is correct
2 Correct 299 ms 295736 KB Output is correct
3 Correct 310 ms 295972 KB Output is correct
4 Correct 273 ms 295800 KB Output is correct
5 Correct 283 ms 295444 KB Output is correct
6 Correct 271 ms 295800 KB Output is correct
7 Correct 269 ms 295672 KB Output is correct
8 Correct 276 ms 295428 KB Output is correct
9 Correct 288 ms 295628 KB Output is correct
10 Correct 283 ms 295672 KB Output is correct
11 Correct 282 ms 295928 KB Output is correct
12 Correct 271 ms 295668 KB Output is correct
13 Correct 267 ms 295032 KB Output is correct
14 Correct 275 ms 295228 KB Output is correct
15 Correct 272 ms 295196 KB Output is correct
16 Correct 266 ms 295160 KB Output is correct
17 Correct 274 ms 297248 KB Output is correct
18 Correct 274 ms 297416 KB Output is correct
19 Correct 276 ms 297228 KB Output is correct
20 Correct 271 ms 296952 KB Output is correct
21 Correct 280 ms 297084 KB Output is correct
22 Correct 272 ms 297180 KB Output is correct
23 Correct 275 ms 297080 KB Output is correct
24 Incorrect 290 ms 296728 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 305744 KB Output is correct
2 Correct 293 ms 304000 KB Output is correct
3 Correct 273 ms 295288 KB Output is correct
4 Correct 284 ms 295160 KB Output is correct
5 Correct 297 ms 304580 KB Output is correct
6 Correct 324 ms 304388 KB Output is correct
7 Correct 323 ms 304520 KB Output is correct
8 Correct 308 ms 303948 KB Output is correct
9 Correct 303 ms 303708 KB Output is correct
10 Correct 301 ms 300444 KB Output is correct
11 Correct 288 ms 303008 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 295244 KB Output is correct
2 Correct 1249 ms 409680 KB Output is correct
3 Correct 2526 ms 522456 KB Output is correct
4 Correct 2474 ms 523468 KB Output is correct
5 Correct 2545 ms 523552 KB Output is correct
6 Correct 600 ms 380288 KB Output is correct
7 Correct 948 ms 463972 KB Output is correct
8 Correct 974 ms 467032 KB Output is correct
9 Correct 270 ms 295040 KB Output is correct
10 Correct 269 ms 295092 KB Output is correct
11 Correct 313 ms 295620 KB Output is correct
12 Correct 269 ms 295544 KB Output is correct
13 Correct 271 ms 295160 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 295160 KB Output is correct
2 Correct 299 ms 295736 KB Output is correct
3 Correct 310 ms 295972 KB Output is correct
4 Correct 273 ms 295800 KB Output is correct
5 Correct 283 ms 295444 KB Output is correct
6 Correct 271 ms 295800 KB Output is correct
7 Correct 269 ms 295672 KB Output is correct
8 Correct 276 ms 295428 KB Output is correct
9 Correct 288 ms 295628 KB Output is correct
10 Correct 283 ms 295672 KB Output is correct
11 Correct 282 ms 295928 KB Output is correct
12 Correct 271 ms 295668 KB Output is correct
13 Correct 267 ms 295032 KB Output is correct
14 Correct 275 ms 295228 KB Output is correct
15 Correct 272 ms 295196 KB Output is correct
16 Correct 266 ms 295160 KB Output is correct
17 Correct 274 ms 297248 KB Output is correct
18 Correct 274 ms 297416 KB Output is correct
19 Correct 276 ms 297228 KB Output is correct
20 Correct 271 ms 296952 KB Output is correct
21 Correct 280 ms 297084 KB Output is correct
22 Correct 272 ms 297180 KB Output is correct
23 Correct 275 ms 297080 KB Output is correct
24 Incorrect 290 ms 296728 KB Output isn't correct