oj.uz

Submission #155615

# Submission time Handle Problem Language Result Execution time Memory
155615 2019-09-29T08:56:11 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 4518 ms 630964 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=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];
unordered_map < ll, bool > bio2, bio3;
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[hashiraj(0, red[x][i].first, red[x][i].second, x)]){
			bio2[hashiraj(0, 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(0, stup[i][x].first, stup[i][x].second, x)]){
			bio3[hashiraj(0, 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;
}*/

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 289 ms 295132 KB Output is correct
2 Correct 291 ms 295568 KB Output is correct
3 Correct 290 ms 295564 KB Output is correct
4 Correct 291 ms 295556 KB Output is correct
5 Correct 301 ms 295416 KB Output is correct
6 Correct 292 ms 295564 KB Output is correct
7 Correct 291 ms 295420 KB Output is correct
8 Correct 291 ms 295152 KB Output is correct
9 Correct 290 ms 295508 KB Output is correct
10 Correct 291 ms 295544 KB Output is correct
11 Correct 292 ms 295572 KB Output is correct
12 Correct 303 ms 295572 KB Output is correct
13 Correct 291 ms 295032 KB Output is correct
14 Correct 301 ms 295244 KB Output is correct
15 Correct 295 ms 295192 KB Output is correct
16 Correct 289 ms 295104 KB Output is correct
17 Correct 288 ms 295032 KB Output is correct
18 Correct 292 ms 295076 KB Output is correct
19 Correct 292 ms 295416 KB Output is correct
20 Correct 290 ms 295528 KB Output is correct
21 Correct 289 ms 295160 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295132 KB Output is correct
2 Correct 291 ms 295568 KB Output is correct
3 Correct 290 ms 295564 KB Output is correct
4 Correct 291 ms 295556 KB Output is correct
5 Correct 301 ms 295416 KB Output is correct
6 Correct 292 ms 295564 KB Output is correct
7 Correct 291 ms 295420 KB Output is correct
8 Correct 291 ms 295152 KB Output is correct
9 Correct 290 ms 295508 KB Output is correct
10 Correct 291 ms 295544 KB Output is correct
11 Correct 292 ms 295572 KB Output is correct
12 Correct 303 ms 295572 KB Output is correct
13 Correct 291 ms 295032 KB Output is correct
14 Correct 301 ms 295244 KB Output is correct
15 Correct 295 ms 295192 KB Output is correct
16 Correct 289 ms 295104 KB Output is correct
17 Correct 323 ms 297144 KB Output is correct
18 Correct 316 ms 297128 KB Output is correct
19 Correct 294 ms 297124 KB Output is correct
20 Correct 293 ms 296408 KB Output is correct
21 Correct 318 ms 296912 KB Output is correct
22 Correct 309 ms 296952 KB Output is correct
23 Correct 295 ms 296960 KB Output is correct
24 Incorrect 294 ms 296440 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295132 KB Output is correct
2 Correct 291 ms 295568 KB Output is correct
3 Correct 290 ms 295564 KB Output is correct
4 Correct 291 ms 295556 KB Output is correct
5 Correct 301 ms 295416 KB Output is correct
6 Correct 292 ms 295564 KB Output is correct
7 Correct 291 ms 295420 KB Output is correct
8 Correct 291 ms 295152 KB Output is correct
9 Correct 290 ms 295508 KB Output is correct
10 Correct 291 ms 295544 KB Output is correct
11 Correct 292 ms 295572 KB Output is correct
12 Correct 303 ms 295572 KB Output is correct
13 Correct 291 ms 295032 KB Output is correct
14 Correct 301 ms 295244 KB Output is correct
15 Correct 295 ms 295192 KB Output is correct
16 Correct 289 ms 295104 KB Output is correct
17 Correct 323 ms 297144 KB Output is correct
18 Correct 316 ms 297128 KB Output is correct
19 Correct 294 ms 297124 KB Output is correct
20 Correct 293 ms 296408 KB Output is correct
21 Correct 318 ms 296912 KB Output is correct
22 Correct 309 ms 296952 KB Output is correct
23 Correct 295 ms 296960 KB Output is correct
24 Incorrect 294 ms 296440 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295132 KB Output is correct
2 Correct 291 ms 295568 KB Output is correct
3 Correct 290 ms 295564 KB Output is correct
4 Correct 291 ms 295556 KB Output is correct
5 Correct 301 ms 295416 KB Output is correct
6 Correct 292 ms 295564 KB Output is correct
7 Correct 291 ms 295420 KB Output is correct
8 Correct 291 ms 295152 KB Output is correct
9 Correct 290 ms 295508 KB Output is correct
10 Correct 291 ms 295544 KB Output is correct
11 Correct 292 ms 295572 KB Output is correct
12 Correct 303 ms 295572 KB Output is correct
13 Correct 291 ms 295032 KB Output is correct
14 Correct 301 ms 295244 KB Output is correct
15 Correct 295 ms 295192 KB Output is correct
16 Correct 289 ms 295104 KB Output is correct
17 Correct 323 ms 297144 KB Output is correct
18 Correct 316 ms 297128 KB Output is correct
19 Correct 294 ms 297124 KB Output is correct
20 Correct 293 ms 296408 KB Output is correct
21 Correct 318 ms 296912 KB Output is correct
22 Correct 309 ms 296952 KB Output is correct
23 Correct 295 ms 296960 KB Output is correct
24 Incorrect 294 ms 296440 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 296292 KB Output is correct
2 Correct 331 ms 295960 KB Output is correct
3 Correct 328 ms 295288 KB Output is correct
4 Correct 292 ms 295092 KB Output is correct
5 Correct 306 ms 296380 KB Output is correct
6 Correct 304 ms 296212 KB Output is correct
7 Correct 300 ms 296292 KB Output is correct
8 Correct 305 ms 296220 KB Output is correct
9 Correct 304 ms 296236 KB Output is correct
10 Correct 314 ms 295544 KB Output is correct
11 Correct 295 ms 295800 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 295160 KB Output is correct
2 Correct 1973 ms 454804 KB Output is correct
3 Correct 4311 ms 629320 KB Output is correct
4 Correct 4518 ms 630804 KB Output is correct
5 Correct 4428 ms 630964 KB Output is correct
6 Correct 702 ms 380524 KB Output is correct
7 Correct 989 ms 464504 KB Output is correct
8 Correct 1075 ms 467704 KB Output is correct
9 Correct 288 ms 295032 KB Output is correct
10 Correct 292 ms 295076 KB Output is correct
11 Correct 292 ms 295416 KB Output is correct
12 Correct 290 ms 295528 KB Output is correct
13 Correct 289 ms 295160 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295132 KB Output is correct
2 Correct 291 ms 295568 KB Output is correct
3 Correct 290 ms 295564 KB Output is correct
4 Correct 291 ms 295556 KB Output is correct
5 Correct 301 ms 295416 KB Output is correct
6 Correct 292 ms 295564 KB Output is correct
7 Correct 291 ms 295420 KB Output is correct
8 Correct 291 ms 295152 KB Output is correct
9 Correct 290 ms 295508 KB Output is correct
10 Correct 291 ms 295544 KB Output is correct
11 Correct 292 ms 295572 KB Output is correct
12 Correct 303 ms 295572 KB Output is correct
13 Correct 291 ms 295032 KB Output is correct
14 Correct 301 ms 295244 KB Output is correct
15 Correct 295 ms 295192 KB Output is correct
16 Correct 289 ms 295104 KB Output is correct
17 Correct 323 ms 297144 KB Output is correct
18 Correct 316 ms 297128 KB Output is correct
19 Correct 294 ms 297124 KB Output is correct
20 Correct 293 ms 296408 KB Output is correct
21 Correct 318 ms 296912 KB Output is correct
22 Correct 309 ms 296952 KB Output is correct
23 Correct 295 ms 296960 KB Output is correct
24 Incorrect 294 ms 296440 KB Output isn't correct