oj.uz

Submission #155616

# Submission time Handle Problem Language Result Execution time Memory
155616 2019-09-29T09:06:15 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 3139 ms 503308 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];
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 292 ms 295180 KB Output is correct
2 Correct 290 ms 295476 KB Output is correct
3 Correct 290 ms 295504 KB Output is correct
4 Correct 294 ms 295492 KB Output is correct
5 Correct 342 ms 295452 KB Output is correct
6 Correct 292 ms 295516 KB Output is correct
7 Correct 290 ms 295416 KB Output is correct
8 Correct 290 ms 295220 KB Output is correct
9 Correct 292 ms 295544 KB Output is correct
10 Correct 302 ms 295528 KB Output is correct
11 Correct 304 ms 295440 KB Output is correct
12 Correct 298 ms 295460 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 290 ms 295288 KB Output is correct
15 Correct 293 ms 295140 KB Output is correct
16 Correct 290 ms 295052 KB Output is correct
17 Correct 288 ms 295032 KB Output is correct
18 Correct 289 ms 295032 KB Output is correct
19 Correct 290 ms 295416 KB Output is correct
20 Correct 292 ms 295568 KB Output is correct
21 Correct 288 ms 295152 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 295180 KB Output is correct
2 Correct 290 ms 295476 KB Output is correct
3 Correct 290 ms 295504 KB Output is correct
4 Correct 294 ms 295492 KB Output is correct
5 Correct 342 ms 295452 KB Output is correct
6 Correct 292 ms 295516 KB Output is correct
7 Correct 290 ms 295416 KB Output is correct
8 Correct 290 ms 295220 KB Output is correct
9 Correct 292 ms 295544 KB Output is correct
10 Correct 302 ms 295528 KB Output is correct
11 Correct 304 ms 295440 KB Output is correct
12 Correct 298 ms 295460 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 290 ms 295288 KB Output is correct
15 Correct 293 ms 295140 KB Output is correct
16 Correct 290 ms 295052 KB Output is correct
17 Correct 293 ms 296624 KB Output is correct
18 Correct 296 ms 296568 KB Output is correct
19 Correct 299 ms 296672 KB Output is correct
20 Correct 308 ms 296312 KB Output is correct
21 Correct 298 ms 296440 KB Output is correct
22 Correct 294 ms 296440 KB Output is correct
23 Correct 326 ms 296568 KB Output is correct
24 Incorrect 334 ms 296240 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 295180 KB Output is correct
2 Correct 290 ms 295476 KB Output is correct
3 Correct 290 ms 295504 KB Output is correct
4 Correct 294 ms 295492 KB Output is correct
5 Correct 342 ms 295452 KB Output is correct
6 Correct 292 ms 295516 KB Output is correct
7 Correct 290 ms 295416 KB Output is correct
8 Correct 290 ms 295220 KB Output is correct
9 Correct 292 ms 295544 KB Output is correct
10 Correct 302 ms 295528 KB Output is correct
11 Correct 304 ms 295440 KB Output is correct
12 Correct 298 ms 295460 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 290 ms 295288 KB Output is correct
15 Correct 293 ms 295140 KB Output is correct
16 Correct 290 ms 295052 KB Output is correct
17 Correct 293 ms 296624 KB Output is correct
18 Correct 296 ms 296568 KB Output is correct
19 Correct 299 ms 296672 KB Output is correct
20 Correct 308 ms 296312 KB Output is correct
21 Correct 298 ms 296440 KB Output is correct
22 Correct 294 ms 296440 KB Output is correct
23 Correct 326 ms 296568 KB Output is correct
24 Incorrect 334 ms 296240 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 295180 KB Output is correct
2 Correct 290 ms 295476 KB Output is correct
3 Correct 290 ms 295504 KB Output is correct
4 Correct 294 ms 295492 KB Output is correct
5 Correct 342 ms 295452 KB Output is correct
6 Correct 292 ms 295516 KB Output is correct
7 Correct 290 ms 295416 KB Output is correct
8 Correct 290 ms 295220 KB Output is correct
9 Correct 292 ms 295544 KB Output is correct
10 Correct 302 ms 295528 KB Output is correct
11 Correct 304 ms 295440 KB Output is correct
12 Correct 298 ms 295460 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 290 ms 295288 KB Output is correct
15 Correct 293 ms 295140 KB Output is correct
16 Correct 290 ms 295052 KB Output is correct
17 Correct 293 ms 296624 KB Output is correct
18 Correct 296 ms 296568 KB Output is correct
19 Correct 299 ms 296672 KB Output is correct
20 Correct 308 ms 296312 KB Output is correct
21 Correct 298 ms 296440 KB Output is correct
22 Correct 294 ms 296440 KB Output is correct
23 Correct 326 ms 296568 KB Output is correct
24 Incorrect 334 ms 296240 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 295588 KB Output is correct
2 Correct 311 ms 295516 KB Output is correct
3 Correct 292 ms 295300 KB Output is correct
4 Correct 304 ms 295084 KB Output is correct
5 Correct 322 ms 295688 KB Output is correct
6 Correct 300 ms 295620 KB Output is correct
7 Correct 299 ms 295612 KB Output is correct
8 Correct 295 ms 295672 KB Output is correct
9 Correct 312 ms 295604 KB Output is correct
10 Correct 303 ms 295448 KB Output is correct
11 Correct 321 ms 295644 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 295160 KB Output is correct
2 Correct 1481 ms 395328 KB Output is correct
3 Correct 3139 ms 502224 KB Output is correct
4 Correct 3004 ms 503108 KB Output is correct
5 Correct 3020 ms 503308 KB Output is correct
6 Correct 557 ms 379940 KB Output is correct
7 Correct 863 ms 463752 KB Output is correct
8 Correct 908 ms 466820 KB Output is correct
9 Correct 288 ms 295032 KB Output is correct
10 Correct 289 ms 295032 KB Output is correct
11 Correct 290 ms 295416 KB Output is correct
12 Correct 292 ms 295568 KB Output is correct
13 Correct 288 ms 295152 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 295180 KB Output is correct
2 Correct 290 ms 295476 KB Output is correct
3 Correct 290 ms 295504 KB Output is correct
4 Correct 294 ms 295492 KB Output is correct
5 Correct 342 ms 295452 KB Output is correct
6 Correct 292 ms 295516 KB Output is correct
7 Correct 290 ms 295416 KB Output is correct
8 Correct 290 ms 295220 KB Output is correct
9 Correct 292 ms 295544 KB Output is correct
10 Correct 302 ms 295528 KB Output is correct
11 Correct 304 ms 295440 KB Output is correct
12 Correct 298 ms 295460 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 290 ms 295288 KB Output is correct
15 Correct 293 ms 295140 KB Output is correct
16 Correct 290 ms 295052 KB Output is correct
17 Correct 293 ms 296624 KB Output is correct
18 Correct 296 ms 296568 KB Output is correct
19 Correct 299 ms 296672 KB Output is correct
20 Correct 308 ms 296312 KB Output is correct
21 Correct 298 ms 296440 KB Output is correct
22 Correct 294 ms 296440 KB Output is correct
23 Correct 326 ms 296568 KB Output is correct
24 Incorrect 334 ms 296240 KB Output isn't correct