oj.uz

Submission #155618

# Submission time Handle Problem Language Result Execution time Memory
155618 2019-09-29T09:26:11 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 3140 ms 507832 KB 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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];
pair < int, int > red[maxn][maxn], stup[maxn][maxn];
map < ll, bool > bio2, bio3;
set < array < int, 4 > > bio;

inline ll hashiraj(ll b, ll c, ll d){
	return 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[hashiraj(red[x][i].first, red[x][i].second, x)]){
			bio2[hashiraj(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[hashiraj(stup[i][x].first, stup[i][x].second, x)]){
			bio3[hashiraj(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);
		bio2.clear();
	}
	for(int i=0; i<m; i++){
		upd2(i);
		bio3.clear();
	}
	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;
}*/

Compilation message

rect.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 299004 KB Output is correct
2 Correct 292 ms 299256 KB Output is correct
3 Correct 320 ms 299212 KB Output is correct
4 Correct 337 ms 299260 KB Output is correct
5 Correct 339 ms 299364 KB Output is correct
6 Correct 335 ms 299228 KB Output is correct
7 Correct 295 ms 299128 KB Output is correct
8 Correct 292 ms 298960 KB Output is correct
9 Correct 293 ms 299256 KB Output is correct
10 Correct 295 ms 299256 KB Output is correct
11 Correct 321 ms 299276 KB Output is correct
12 Correct 302 ms 299128 KB Output is correct
13 Correct 320 ms 298744 KB Output is correct
14 Correct 318 ms 298952 KB Output is correct
15 Correct 305 ms 298892 KB Output is correct
16 Correct 290 ms 298872 KB Output is correct
17 Correct 295 ms 298744 KB Output is correct
18 Correct 294 ms 298872 KB Output is correct
19 Correct 293 ms 299260 KB Output is correct
20 Correct 292 ms 299128 KB Output is correct
21 Correct 294 ms 299000 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 299004 KB Output is correct
2 Correct 292 ms 299256 KB Output is correct
3 Correct 320 ms 299212 KB Output is correct
4 Correct 337 ms 299260 KB Output is correct
5 Correct 339 ms 299364 KB Output is correct
6 Correct 335 ms 299228 KB Output is correct
7 Correct 295 ms 299128 KB Output is correct
8 Correct 292 ms 298960 KB Output is correct
9 Correct 293 ms 299256 KB Output is correct
10 Correct 295 ms 299256 KB Output is correct
11 Correct 321 ms 299276 KB Output is correct
12 Correct 302 ms 299128 KB Output is correct
13 Correct 320 ms 298744 KB Output is correct
14 Correct 318 ms 298952 KB Output is correct
15 Correct 305 ms 298892 KB Output is correct
16 Correct 290 ms 298872 KB Output is correct
17 Correct 299 ms 300336 KB Output is correct
18 Correct 299 ms 300340 KB Output is correct
19 Correct 312 ms 300508 KB Output is correct
20 Correct 304 ms 300008 KB Output is correct
21 Correct 298 ms 300284 KB Output is correct
22 Correct 296 ms 300156 KB Output is correct
23 Correct 297 ms 300152 KB Output is correct
24 Incorrect 294 ms 300024 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 299004 KB Output is correct
2 Correct 292 ms 299256 KB Output is correct
3 Correct 320 ms 299212 KB Output is correct
4 Correct 337 ms 299260 KB Output is correct
5 Correct 339 ms 299364 KB Output is correct
6 Correct 335 ms 299228 KB Output is correct
7 Correct 295 ms 299128 KB Output is correct
8 Correct 292 ms 298960 KB Output is correct
9 Correct 293 ms 299256 KB Output is correct
10 Correct 295 ms 299256 KB Output is correct
11 Correct 321 ms 299276 KB Output is correct
12 Correct 302 ms 299128 KB Output is correct
13 Correct 320 ms 298744 KB Output is correct
14 Correct 318 ms 298952 KB Output is correct
15 Correct 305 ms 298892 KB Output is correct
16 Correct 290 ms 298872 KB Output is correct
17 Correct 299 ms 300336 KB Output is correct
18 Correct 299 ms 300340 KB Output is correct
19 Correct 312 ms 300508 KB Output is correct
20 Correct 304 ms 300008 KB Output is correct
21 Correct 298 ms 300284 KB Output is correct
22 Correct 296 ms 300156 KB Output is correct
23 Correct 297 ms 300152 KB Output is correct
24 Incorrect 294 ms 300024 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 299004 KB Output is correct
2 Correct 292 ms 299256 KB Output is correct
3 Correct 320 ms 299212 KB Output is correct
4 Correct 337 ms 299260 KB Output is correct
5 Correct 339 ms 299364 KB Output is correct
6 Correct 335 ms 299228 KB Output is correct
7 Correct 295 ms 299128 KB Output is correct
8 Correct 292 ms 298960 KB Output is correct
9 Correct 293 ms 299256 KB Output is correct
10 Correct 295 ms 299256 KB Output is correct
11 Correct 321 ms 299276 KB Output is correct
12 Correct 302 ms 299128 KB Output is correct
13 Correct 320 ms 298744 KB Output is correct
14 Correct 318 ms 298952 KB Output is correct
15 Correct 305 ms 298892 KB Output is correct
16 Correct 290 ms 298872 KB Output is correct
17 Correct 299 ms 300336 KB Output is correct
18 Correct 299 ms 300340 KB Output is correct
19 Correct 312 ms 300508 KB Output is correct
20 Correct 304 ms 300008 KB Output is correct
21 Correct 298 ms 300284 KB Output is correct
22 Correct 296 ms 300156 KB Output is correct
23 Correct 297 ms 300152 KB Output is correct
24 Incorrect 294 ms 300024 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 299324 KB Output is correct
2 Correct 299 ms 299240 KB Output is correct
3 Correct 297 ms 299128 KB Output is correct
4 Correct 293 ms 298848 KB Output is correct
5 Correct 318 ms 299500 KB Output is correct
6 Correct 317 ms 299384 KB Output is correct
7 Correct 298 ms 299512 KB Output is correct
8 Correct 299 ms 299404 KB Output is correct
9 Correct 301 ms 299332 KB Output is correct
10 Correct 294 ms 299256 KB Output is correct
11 Correct 298 ms 299256 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 298936 KB Output is correct
2 Correct 1442 ms 399476 KB Output is correct
3 Correct 3064 ms 506632 KB Output is correct
4 Correct 3140 ms 507656 KB Output is correct
5 Correct 3028 ms 507832 KB Output is correct
6 Correct 579 ms 384112 KB Output is correct
7 Correct 903 ms 468280 KB Output is correct
8 Correct 918 ms 471380 KB Output is correct
9 Correct 295 ms 298744 KB Output is correct
10 Correct 294 ms 298872 KB Output is correct
11 Correct 293 ms 299260 KB Output is correct
12 Correct 292 ms 299128 KB Output is correct
13 Correct 294 ms 299000 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 299004 KB Output is correct
2 Correct 292 ms 299256 KB Output is correct
3 Correct 320 ms 299212 KB Output is correct
4 Correct 337 ms 299260 KB Output is correct
5 Correct 339 ms 299364 KB Output is correct
6 Correct 335 ms 299228 KB Output is correct
7 Correct 295 ms 299128 KB Output is correct
8 Correct 292 ms 298960 KB Output is correct
9 Correct 293 ms 299256 KB Output is correct
10 Correct 295 ms 299256 KB Output is correct
11 Correct 321 ms 299276 KB Output is correct
12 Correct 302 ms 299128 KB Output is correct
13 Correct 320 ms 298744 KB Output is correct
14 Correct 318 ms 298952 KB Output is correct
15 Correct 305 ms 298892 KB Output is correct
16 Correct 290 ms 298872 KB Output is correct
17 Correct 299 ms 300336 KB Output is correct
18 Correct 299 ms 300340 KB Output is correct
19 Correct 312 ms 300508 KB Output is correct
20 Correct 304 ms 300008 KB Output is correct
21 Correct 298 ms 300284 KB Output is correct
22 Correct 296 ms 300156 KB Output is correct
23 Correct 297 ms 300152 KB Output is correct
24 Incorrect 294 ms 300024 KB Output isn't correct