oj.uz

Submission #155601

# Submission time Handle Problem Language Result Execution time Memory
155601 2019-09-29T08:07:14 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 2674 ms 523700 KB 
#include "rect.h"
#include <cstdio>
#include <vector>	
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <array>

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;
set < array < int, 4 > > 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, 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.find({r1, r2, c1, c2})==bio.end()){
//			printf("cudo\n");
			bio.insert({r1, r2, c1, c2});
			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 267 ms 295160 KB Output is correct
2 Correct 268 ms 295688 KB Output is correct
3 Correct 270 ms 295744 KB Output is correct
4 Correct 272 ms 295744 KB Output is correct
5 Correct 268 ms 295492 KB Output is correct
6 Correct 269 ms 295672 KB Output is correct
7 Correct 269 ms 295544 KB Output is correct
8 Correct 269 ms 295416 KB Output is correct
9 Correct 268 ms 295672 KB Output is correct
10 Correct 279 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 276 ms 295824 KB Output is correct
13 Correct 269 ms 295032 KB Output is correct
14 Correct 276 ms 295164 KB Output is correct
15 Correct 303 ms 295288 KB Output is correct
16 Correct 268 ms 295160 KB Output is correct
17 Correct 296 ms 295160 KB Output is correct
18 Correct 275 ms 295048 KB Output is correct
19 Correct 283 ms 295724 KB Output is correct
20 Correct 270 ms 295416 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 267 ms 295160 KB Output is correct
2 Correct 268 ms 295688 KB Output is correct
3 Correct 270 ms 295744 KB Output is correct
4 Correct 272 ms 295744 KB Output is correct
5 Correct 268 ms 295492 KB Output is correct
6 Correct 269 ms 295672 KB Output is correct
7 Correct 269 ms 295544 KB Output is correct
8 Correct 269 ms 295416 KB Output is correct
9 Correct 268 ms 295672 KB Output is correct
10 Correct 279 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 276 ms 295824 KB Output is correct
13 Correct 269 ms 295032 KB Output is correct
14 Correct 276 ms 295164 KB Output is correct
15 Correct 303 ms 295288 KB Output is correct
16 Correct 268 ms 295160 KB Output is correct
17 Correct 272 ms 297208 KB Output is correct
18 Correct 272 ms 297432 KB Output is correct
19 Correct 284 ms 297420 KB Output is correct
20 Correct 279 ms 297000 KB Output is correct
21 Correct 273 ms 297080 KB Output is correct
22 Correct 283 ms 297032 KB Output is correct
23 Correct 273 ms 297080 KB Output is correct
24 Incorrect 275 ms 296696 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 295160 KB Output is correct
2 Correct 268 ms 295688 KB Output is correct
3 Correct 270 ms 295744 KB Output is correct
4 Correct 272 ms 295744 KB Output is correct
5 Correct 268 ms 295492 KB Output is correct
6 Correct 269 ms 295672 KB Output is correct
7 Correct 269 ms 295544 KB Output is correct
8 Correct 269 ms 295416 KB Output is correct
9 Correct 268 ms 295672 KB Output is correct
10 Correct 279 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 276 ms 295824 KB Output is correct
13 Correct 269 ms 295032 KB Output is correct
14 Correct 276 ms 295164 KB Output is correct
15 Correct 303 ms 295288 KB Output is correct
16 Correct 268 ms 295160 KB Output is correct
17 Correct 272 ms 297208 KB Output is correct
18 Correct 272 ms 297432 KB Output is correct
19 Correct 284 ms 297420 KB Output is correct
20 Correct 279 ms 297000 KB Output is correct
21 Correct 273 ms 297080 KB Output is correct
22 Correct 283 ms 297032 KB Output is correct
23 Correct 273 ms 297080 KB Output is correct
24 Incorrect 275 ms 296696 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 295160 KB Output is correct
2 Correct 268 ms 295688 KB Output is correct
3 Correct 270 ms 295744 KB Output is correct
4 Correct 272 ms 295744 KB Output is correct
5 Correct 268 ms 295492 KB Output is correct
6 Correct 269 ms 295672 KB Output is correct
7 Correct 269 ms 295544 KB Output is correct
8 Correct 269 ms 295416 KB Output is correct
9 Correct 268 ms 295672 KB Output is correct
10 Correct 279 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 276 ms 295824 KB Output is correct
13 Correct 269 ms 295032 KB Output is correct
14 Correct 276 ms 295164 KB Output is correct
15 Correct 303 ms 295288 KB Output is correct
16 Correct 268 ms 295160 KB Output is correct
17 Correct 272 ms 297208 KB Output is correct
18 Correct 272 ms 297432 KB Output is correct
19 Correct 284 ms 297420 KB Output is correct
20 Correct 279 ms 297000 KB Output is correct
21 Correct 273 ms 297080 KB Output is correct
22 Correct 283 ms 297032 KB Output is correct
23 Correct 273 ms 297080 KB Output is correct
24 Incorrect 275 ms 296696 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 305696 KB Output is correct
2 Correct 281 ms 303992 KB Output is correct
3 Correct 271 ms 295348 KB Output is correct
4 Correct 269 ms 295052 KB Output is correct
5 Correct 280 ms 304632 KB Output is correct
6 Correct 281 ms 304452 KB Output is correct
7 Correct 288 ms 304472 KB Output is correct
8 Correct 282 ms 303840 KB Output is correct
9 Correct 322 ms 303736 KB Output is correct
10 Correct 290 ms 300384 KB Output is correct
11 Correct 285 ms 303096 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 295288 KB Output is correct
2 Correct 1270 ms 409672 KB Output is correct
3 Correct 2620 ms 522420 KB Output is correct
4 Correct 2532 ms 523432 KB Output is correct
5 Correct 2674 ms 523700 KB Output is correct
6 Correct 670 ms 380124 KB Output is correct
7 Correct 953 ms 463792 KB Output is correct
8 Correct 998 ms 466932 KB Output is correct
9 Correct 296 ms 295160 KB Output is correct
10 Correct 275 ms 295048 KB Output is correct
11 Correct 283 ms 295724 KB Output is correct
12 Correct 270 ms 295416 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 267 ms 295160 KB Output is correct
2 Correct 268 ms 295688 KB Output is correct
3 Correct 270 ms 295744 KB Output is correct
4 Correct 272 ms 295744 KB Output is correct
5 Correct 268 ms 295492 KB Output is correct
6 Correct 269 ms 295672 KB Output is correct
7 Correct 269 ms 295544 KB Output is correct
8 Correct 269 ms 295416 KB Output is correct
9 Correct 268 ms 295672 KB Output is correct
10 Correct 279 ms 295672 KB Output is correct
11 Correct 271 ms 295672 KB Output is correct
12 Correct 276 ms 295824 KB Output is correct
13 Correct 269 ms 295032 KB Output is correct
14 Correct 276 ms 295164 KB Output is correct
15 Correct 303 ms 295288 KB Output is correct
16 Correct 268 ms 295160 KB Output is correct
17 Correct 272 ms 297208 KB Output is correct
18 Correct 272 ms 297432 KB Output is correct
19 Correct 284 ms 297420 KB Output is correct
20 Correct 279 ms 297000 KB Output is correct
21 Correct 273 ms 297080 KB Output is correct
22 Correct 283 ms 297032 KB Output is correct
23 Correct 273 ms 297080 KB Output is correct
24 Incorrect 275 ms 296696 KB Output isn't correct