oj.uz

Submission #155624

# Submission time Handle Problem Language Result Execution time Memory
155624 2019-09-29T10:10:26 Z vanic Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 584708 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;
map < ll, bool > bio4, bio5;
set < array < int, 4 > > bio;

inline ll hashiraj(ll b, ll c, ll d){
	return b*maxn*maxn+c*maxn+d;
}
 
bool 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(!bio4[hashiraj(red[x][i].first, red[x][i].second, x)]){
			if(bio2[hashiraj(red[x][i].first, red[x][i].second, x)]){
				return 1;
			}
			else{
				bio2[hashiraj(red[x][i].first, red[x][i].second, x)]=1;
				bio4[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));
	}
	return 0;
}
 
bool 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(!bio5[hashiraj(stup[i][x].first, stup[i][x].second, x)]){
			if(bio3[hashiraj(stup[i][x].first, stup[i][x].second, x)]){
				return 1;
			}
			else{
				bio3[hashiraj(stup[i][x].first, stup[i][x].second, x)]=1;
				bio5[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));
	}
	return 0;
}
 
 
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++){
		if(upd1(i)){
			return -1;
		}
		bio4.clear();
	}
	for(int i=0; i<m; i++){
		if(upd2(i)){
			return -1;
		}
		bio5.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);
		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++;
			}
		}
	}
	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 330 ms 298872 KB Output is correct
2 Correct 395 ms 299512 KB Output is correct
3 Correct 323 ms 299356 KB Output is correct
4 Correct 294 ms 299384 KB Output is correct
5 Correct 297 ms 299228 KB Output is correct
6 Correct 298 ms 299408 KB Output is correct
7 Correct 294 ms 299256 KB Output is correct
8 Correct 293 ms 299000 KB Output is correct
9 Correct 298 ms 299312 KB Output is correct
10 Correct 334 ms 299256 KB Output is correct
11 Correct 307 ms 299384 KB Output is correct
12 Correct 350 ms 299384 KB Output is correct
13 Correct 308 ms 298900 KB Output is correct
14 Correct 317 ms 298912 KB Output is correct
15 Correct 302 ms 299004 KB Output is correct
16 Correct 296 ms 298900 KB Output is correct
17 Correct 337 ms 298904 KB Output is correct
18 Correct 317 ms 298916 KB Output is correct
19 Correct 301 ms 299260 KB Output is correct
20 Correct 298 ms 299256 KB Output is correct
21 Correct 324 ms 299004 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 298872 KB Output is correct
2 Correct 395 ms 299512 KB Output is correct
3 Correct 323 ms 299356 KB Output is correct
4 Correct 294 ms 299384 KB Output is correct
5 Correct 297 ms 299228 KB Output is correct
6 Correct 298 ms 299408 KB Output is correct
7 Correct 294 ms 299256 KB Output is correct
8 Correct 293 ms 299000 KB Output is correct
9 Correct 298 ms 299312 KB Output is correct
10 Correct 334 ms 299256 KB Output is correct
11 Correct 307 ms 299384 KB Output is correct
12 Correct 350 ms 299384 KB Output is correct
13 Correct 308 ms 298900 KB Output is correct
14 Correct 317 ms 298912 KB Output is correct
15 Correct 302 ms 299004 KB Output is correct
16 Correct 296 ms 298900 KB Output is correct
17 Correct 314 ms 301256 KB Output is correct
18 Correct 304 ms 301276 KB Output is correct
19 Correct 311 ms 301180 KB Output is correct
20 Correct 299 ms 300380 KB Output is correct
21 Correct 318 ms 301048 KB Output is correct
22 Correct 336 ms 300908 KB Output is correct
23 Correct 353 ms 300920 KB Output is correct
24 Correct 324 ms 300408 KB Output is correct
25 Correct 337 ms 298904 KB Output is correct
26 Correct 317 ms 298916 KB Output is correct
27 Correct 301 ms 299260 KB Output is correct
28 Correct 298 ms 299256 KB Output is correct
29 Correct 324 ms 299004 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 298872 KB Output is correct
2 Correct 395 ms 299512 KB Output is correct
3 Correct 323 ms 299356 KB Output is correct
4 Correct 294 ms 299384 KB Output is correct
5 Correct 297 ms 299228 KB Output is correct
6 Correct 298 ms 299408 KB Output is correct
7 Correct 294 ms 299256 KB Output is correct
8 Correct 293 ms 299000 KB Output is correct
9 Correct 298 ms 299312 KB Output is correct
10 Correct 334 ms 299256 KB Output is correct
11 Correct 307 ms 299384 KB Output is correct
12 Correct 350 ms 299384 KB Output is correct
13 Correct 308 ms 298900 KB Output is correct
14 Correct 317 ms 298912 KB Output is correct
15 Correct 302 ms 299004 KB Output is correct
16 Correct 296 ms 298900 KB Output is correct
17 Correct 314 ms 301256 KB Output is correct
18 Correct 304 ms 301276 KB Output is correct
19 Correct 311 ms 301180 KB Output is correct
20 Correct 299 ms 300380 KB Output is correct
21 Correct 318 ms 301048 KB Output is correct
22 Correct 336 ms 300908 KB Output is correct
23 Correct 353 ms 300920 KB Output is correct
24 Correct 324 ms 300408 KB Output is correct
25 Correct 452 ms 310424 KB Output is correct
26 Correct 437 ms 310396 KB Output is correct
27 Correct 404 ms 310356 KB Output is correct
28 Correct 330 ms 304836 KB Output is correct
29 Correct 411 ms 308944 KB Output is correct
30 Correct 383 ms 308828 KB Output is correct
31 Correct 373 ms 308472 KB Output is correct
32 Correct 372 ms 308348 KB Output is correct
33 Correct 337 ms 298904 KB Output is correct
34 Correct 317 ms 298916 KB Output is correct
35 Correct 301 ms 299260 KB Output is correct
36 Correct 298 ms 299256 KB Output is correct
37 Correct 324 ms 299004 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 298872 KB Output is correct
2 Correct 395 ms 299512 KB Output is correct
3 Correct 323 ms 299356 KB Output is correct
4 Correct 294 ms 299384 KB Output is correct
5 Correct 297 ms 299228 KB Output is correct
6 Correct 298 ms 299408 KB Output is correct
7 Correct 294 ms 299256 KB Output is correct
8 Correct 293 ms 299000 KB Output is correct
9 Correct 298 ms 299312 KB Output is correct
10 Correct 334 ms 299256 KB Output is correct
11 Correct 307 ms 299384 KB Output is correct
12 Correct 350 ms 299384 KB Output is correct
13 Correct 308 ms 298900 KB Output is correct
14 Correct 317 ms 298912 KB Output is correct
15 Correct 302 ms 299004 KB Output is correct
16 Correct 296 ms 298900 KB Output is correct
17 Correct 314 ms 301256 KB Output is correct
18 Correct 304 ms 301276 KB Output is correct
19 Correct 311 ms 301180 KB Output is correct
20 Correct 299 ms 300380 KB Output is correct
21 Correct 318 ms 301048 KB Output is correct
22 Correct 336 ms 300908 KB Output is correct
23 Correct 353 ms 300920 KB Output is correct
24 Correct 324 ms 300408 KB Output is correct
25 Correct 452 ms 310424 KB Output is correct
26 Correct 437 ms 310396 KB Output is correct
27 Correct 404 ms 310356 KB Output is correct
28 Correct 330 ms 304836 KB Output is correct
29 Correct 411 ms 308944 KB Output is correct
30 Correct 383 ms 308828 KB Output is correct
31 Correct 373 ms 308472 KB Output is correct
32 Correct 372 ms 308348 KB Output is correct
33 Correct 1764 ms 400384 KB Output is correct
34 Correct 1535 ms 400540 KB Output is correct
35 Correct 1423 ms 400456 KB Output is correct
36 Correct 1365 ms 400536 KB Output is correct
37 Correct 1929 ms 418516 KB Output is correct
38 Correct 1924 ms 418288 KB Output is correct
39 Correct 1884 ms 418364 KB Output is correct
40 Correct 1818 ms 410664 KB Output is correct
41 Correct 729 ms 339136 KB Output is correct
42 Correct 1176 ms 350284 KB Output is correct
43 Correct 2066 ms 398508 KB Output is correct
44 Correct 2307 ms 399632 KB Output is correct
45 Correct 1069 ms 353528 KB Output is correct
46 Correct 1049 ms 349304 KB Output is correct
47 Correct 2209 ms 393140 KB Output is correct
48 Correct 2299 ms 393444 KB Output is correct
49 Correct 337 ms 298904 KB Output is correct
50 Correct 317 ms 298916 KB Output is correct
51 Correct 301 ms 299260 KB Output is correct
52 Correct 298 ms 299256 KB Output is correct
53 Correct 324 ms 299004 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 300152 KB Output is correct
2 Correct 302 ms 300024 KB Output is correct
3 Correct 297 ms 299260 KB Output is correct
4 Correct 296 ms 298836 KB Output is correct
5 Correct 304 ms 300272 KB Output is correct
6 Correct 305 ms 300160 KB Output is correct
7 Correct 356 ms 300260 KB Output is correct
8 Correct 328 ms 300208 KB Output is correct
9 Correct 304 ms 300100 KB Output is correct
10 Correct 299 ms 299388 KB Output is correct
11 Correct 309 ms 299848 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 298956 KB Output is correct
2 Correct 3623 ms 489820 KB Output is correct
3 Execution timed out 5077 ms 584708 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 298872 KB Output is correct
2 Correct 395 ms 299512 KB Output is correct
3 Correct 323 ms 299356 KB Output is correct
4 Correct 294 ms 299384 KB Output is correct
5 Correct 297 ms 299228 KB Output is correct
6 Correct 298 ms 299408 KB Output is correct
7 Correct 294 ms 299256 KB Output is correct
8 Correct 293 ms 299000 KB Output is correct
9 Correct 298 ms 299312 KB Output is correct
10 Correct 334 ms 299256 KB Output is correct
11 Correct 307 ms 299384 KB Output is correct
12 Correct 350 ms 299384 KB Output is correct
13 Correct 308 ms 298900 KB Output is correct
14 Correct 317 ms 298912 KB Output is correct
15 Correct 302 ms 299004 KB Output is correct
16 Correct 296 ms 298900 KB Output is correct
17 Correct 314 ms 301256 KB Output is correct
18 Correct 304 ms 301276 KB Output is correct
19 Correct 311 ms 301180 KB Output is correct
20 Correct 299 ms 300380 KB Output is correct
21 Correct 318 ms 301048 KB Output is correct
22 Correct 336 ms 300908 KB Output is correct
23 Correct 353 ms 300920 KB Output is correct
24 Correct 324 ms 300408 KB Output is correct
25 Correct 452 ms 310424 KB Output is correct
26 Correct 437 ms 310396 KB Output is correct
27 Correct 404 ms 310356 KB Output is correct
28 Correct 330 ms 304836 KB Output is correct
29 Correct 411 ms 308944 KB Output is correct
30 Correct 383 ms 308828 KB Output is correct
31 Correct 373 ms 308472 KB Output is correct
32 Correct 372 ms 308348 KB Output is correct
33 Correct 1764 ms 400384 KB Output is correct
34 Correct 1535 ms 400540 KB Output is correct
35 Correct 1423 ms 400456 KB Output is correct
36 Correct 1365 ms 400536 KB Output is correct
37 Correct 1929 ms 418516 KB Output is correct
38 Correct 1924 ms 418288 KB Output is correct
39 Correct 1884 ms 418364 KB Output is correct
40 Correct 1818 ms 410664 KB Output is correct
41 Correct 729 ms 339136 KB Output is correct
42 Correct 1176 ms 350284 KB Output is correct
43 Correct 2066 ms 398508 KB Output is correct
44 Correct 2307 ms 399632 KB Output is correct
45 Correct 1069 ms 353528 KB Output is correct
46 Correct 1049 ms 349304 KB Output is correct
47 Correct 2209 ms 393140 KB Output is correct
48 Correct 2299 ms 393444 KB Output is correct
49 Correct 307 ms 300152 KB Output is correct
50 Correct 302 ms 300024 KB Output is correct
51 Correct 297 ms 299260 KB Output is correct
52 Correct 296 ms 298836 KB Output is correct
53 Correct 304 ms 300272 KB Output is correct
54 Correct 305 ms 300160 KB Output is correct
55 Correct 356 ms 300260 KB Output is correct
56 Correct 328 ms 300208 KB Output is correct
57 Correct 304 ms 300100 KB Output is correct
58 Correct 299 ms 299388 KB Output is correct
59 Correct 309 ms 299848 KB Output is correct
60 Correct 294 ms 298956 KB Output is correct
61 Correct 3623 ms 489820 KB Output is correct
62 Execution timed out 5077 ms 584708 KB Time limit exceeded
63 Halted 0 ms 0 KB -