oj.uz

Submission #155609

# Submission time Handle Problem Language Result Execution time Memory
155609 2019-09-29T08:30:35 Z vanic Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 597392 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>
 
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 > bio, bio2, bio3;
 
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[hashiraj(r1, r2, c1, c2)]){
//			printf("cudo\n");
			bio[hashiraj(r1, r2, c1, c2)]=1;
			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 286 ms 295056 KB Output is correct
2 Correct 310 ms 295552 KB Output is correct
3 Correct 306 ms 295636 KB Output is correct
4 Correct 288 ms 295644 KB Output is correct
5 Correct 289 ms 295356 KB Output is correct
6 Correct 327 ms 295588 KB Output is correct
7 Correct 307 ms 295556 KB Output is correct
8 Correct 300 ms 295176 KB Output is correct
9 Correct 337 ms 295496 KB Output is correct
10 Correct 291 ms 295672 KB Output is correct
11 Correct 289 ms 295544 KB Output is correct
12 Correct 299 ms 295544 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 286 ms 295356 KB Output is correct
15 Correct 288 ms 295288 KB Output is correct
16 Correct 286 ms 295032 KB Output is correct
17 Correct 286 ms 295052 KB Output is correct
18 Correct 300 ms 295104 KB Output is correct
19 Correct 289 ms 295416 KB Output is correct
20 Correct 292 ms 295420 KB Output is correct
21 Correct 291 ms 295248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 295056 KB Output is correct
2 Correct 310 ms 295552 KB Output is correct
3 Correct 306 ms 295636 KB Output is correct
4 Correct 288 ms 295644 KB Output is correct
5 Correct 289 ms 295356 KB Output is correct
6 Correct 327 ms 295588 KB Output is correct
7 Correct 307 ms 295556 KB Output is correct
8 Correct 300 ms 295176 KB Output is correct
9 Correct 337 ms 295496 KB Output is correct
10 Correct 291 ms 295672 KB Output is correct
11 Correct 289 ms 295544 KB Output is correct
12 Correct 299 ms 295544 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 286 ms 295356 KB Output is correct
15 Correct 288 ms 295288 KB Output is correct
16 Correct 286 ms 295032 KB Output is correct
17 Correct 314 ms 297464 KB Output is correct
18 Correct 295 ms 297464 KB Output is correct
19 Correct 306 ms 297504 KB Output is correct
20 Correct 292 ms 296712 KB Output is correct
21 Correct 297 ms 297256 KB Output is correct
22 Correct 295 ms 297160 KB Output is correct
23 Correct 295 ms 297208 KB Output is correct
24 Correct 292 ms 296548 KB Output is correct
25 Correct 286 ms 295052 KB Output is correct
26 Correct 300 ms 295104 KB Output is correct
27 Correct 289 ms 295416 KB Output is correct
28 Correct 292 ms 295420 KB Output is correct
29 Correct 291 ms 295248 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 295056 KB Output is correct
2 Correct 310 ms 295552 KB Output is correct
3 Correct 306 ms 295636 KB Output is correct
4 Correct 288 ms 295644 KB Output is correct
5 Correct 289 ms 295356 KB Output is correct
6 Correct 327 ms 295588 KB Output is correct
7 Correct 307 ms 295556 KB Output is correct
8 Correct 300 ms 295176 KB Output is correct
9 Correct 337 ms 295496 KB Output is correct
10 Correct 291 ms 295672 KB Output is correct
11 Correct 289 ms 295544 KB Output is correct
12 Correct 299 ms 295544 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 286 ms 295356 KB Output is correct
15 Correct 288 ms 295288 KB Output is correct
16 Correct 286 ms 295032 KB Output is correct
17 Correct 314 ms 297464 KB Output is correct
18 Correct 295 ms 297464 KB Output is correct
19 Correct 306 ms 297504 KB Output is correct
20 Correct 292 ms 296712 KB Output is correct
21 Correct 297 ms 297256 KB Output is correct
22 Correct 295 ms 297160 KB Output is correct
23 Correct 295 ms 297208 KB Output is correct
24 Correct 292 ms 296548 KB Output is correct
25 Correct 356 ms 306424 KB Output is correct
26 Correct 356 ms 306476 KB Output is correct
27 Correct 359 ms 306504 KB Output is correct
28 Correct 317 ms 301092 KB Output is correct
29 Correct 361 ms 305072 KB Output is correct
30 Correct 356 ms 305192 KB Output is correct
31 Correct 356 ms 304632 KB Output is correct
32 Correct 350 ms 304504 KB Output is correct
33 Correct 286 ms 295052 KB Output is correct
34 Correct 300 ms 295104 KB Output is correct
35 Correct 289 ms 295416 KB Output is correct
36 Correct 292 ms 295420 KB Output is correct
37 Correct 291 ms 295248 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 295056 KB Output is correct
2 Correct 310 ms 295552 KB Output is correct
3 Correct 306 ms 295636 KB Output is correct
4 Correct 288 ms 295644 KB Output is correct
5 Correct 289 ms 295356 KB Output is correct
6 Correct 327 ms 295588 KB Output is correct
7 Correct 307 ms 295556 KB Output is correct
8 Correct 300 ms 295176 KB Output is correct
9 Correct 337 ms 295496 KB Output is correct
10 Correct 291 ms 295672 KB Output is correct
11 Correct 289 ms 295544 KB Output is correct
12 Correct 299 ms 295544 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 286 ms 295356 KB Output is correct
15 Correct 288 ms 295288 KB Output is correct
16 Correct 286 ms 295032 KB Output is correct
17 Correct 314 ms 297464 KB Output is correct
18 Correct 295 ms 297464 KB Output is correct
19 Correct 306 ms 297504 KB Output is correct
20 Correct 292 ms 296712 KB Output is correct
21 Correct 297 ms 297256 KB Output is correct
22 Correct 295 ms 297160 KB Output is correct
23 Correct 295 ms 297208 KB Output is correct
24 Correct 292 ms 296548 KB Output is correct
25 Correct 356 ms 306424 KB Output is correct
26 Correct 356 ms 306476 KB Output is correct
27 Correct 359 ms 306504 KB Output is correct
28 Correct 317 ms 301092 KB Output is correct
29 Correct 361 ms 305072 KB Output is correct
30 Correct 356 ms 305192 KB Output is correct
31 Correct 356 ms 304632 KB Output is correct
32 Correct 350 ms 304504 KB Output is correct
33 Correct 1263 ms 396860 KB Output is correct
34 Correct 1134 ms 396732 KB Output is correct
35 Correct 1127 ms 396932 KB Output is correct
36 Correct 1125 ms 396756 KB Output is correct
37 Correct 1491 ms 414884 KB Output is correct
38 Correct 1594 ms 414536 KB Output is correct
39 Correct 1514 ms 414772 KB Output is correct
40 Correct 1491 ms 407208 KB Output is correct
41 Correct 682 ms 335432 KB Output is correct
42 Correct 929 ms 346532 KB Output is correct
43 Correct 1772 ms 394528 KB Output is correct
44 Correct 1790 ms 395640 KB Output is correct
45 Correct 1008 ms 349668 KB Output is correct
46 Correct 934 ms 345484 KB Output is correct
47 Correct 2017 ms 389388 KB Output is correct
48 Correct 1551 ms 389780 KB Output is correct
49 Correct 286 ms 295052 KB Output is correct
50 Correct 300 ms 295104 KB Output is correct
51 Correct 289 ms 295416 KB Output is correct
52 Correct 292 ms 295420 KB Output is correct
53 Correct 291 ms 295248 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 296424 KB Output is correct
2 Correct 293 ms 296196 KB Output is correct
3 Correct 287 ms 295516 KB Output is correct
4 Correct 290 ms 295112 KB Output is correct
5 Correct 296 ms 296564 KB Output is correct
6 Correct 312 ms 296580 KB Output is correct
7 Correct 293 ms 296452 KB Output is correct
8 Correct 295 ms 296456 KB Output is correct
9 Correct 305 ms 296388 KB Output is correct
10 Correct 325 ms 295448 KB Output is correct
11 Correct 289 ms 295992 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 295296 KB Output is correct
2 Correct 3406 ms 485628 KB Output is correct
3 Execution timed out 5126 ms 597392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 295056 KB Output is correct
2 Correct 310 ms 295552 KB Output is correct
3 Correct 306 ms 295636 KB Output is correct
4 Correct 288 ms 295644 KB Output is correct
5 Correct 289 ms 295356 KB Output is correct
6 Correct 327 ms 295588 KB Output is correct
7 Correct 307 ms 295556 KB Output is correct
8 Correct 300 ms 295176 KB Output is correct
9 Correct 337 ms 295496 KB Output is correct
10 Correct 291 ms 295672 KB Output is correct
11 Correct 289 ms 295544 KB Output is correct
12 Correct 299 ms 295544 KB Output is correct
13 Correct 292 ms 295032 KB Output is correct
14 Correct 286 ms 295356 KB Output is correct
15 Correct 288 ms 295288 KB Output is correct
16 Correct 286 ms 295032 KB Output is correct
17 Correct 314 ms 297464 KB Output is correct
18 Correct 295 ms 297464 KB Output is correct
19 Correct 306 ms 297504 KB Output is correct
20 Correct 292 ms 296712 KB Output is correct
21 Correct 297 ms 297256 KB Output is correct
22 Correct 295 ms 297160 KB Output is correct
23 Correct 295 ms 297208 KB Output is correct
24 Correct 292 ms 296548 KB Output is correct
25 Correct 356 ms 306424 KB Output is correct
26 Correct 356 ms 306476 KB Output is correct
27 Correct 359 ms 306504 KB Output is correct
28 Correct 317 ms 301092 KB Output is correct
29 Correct 361 ms 305072 KB Output is correct
30 Correct 356 ms 305192 KB Output is correct
31 Correct 356 ms 304632 KB Output is correct
32 Correct 350 ms 304504 KB Output is correct
33 Correct 1263 ms 396860 KB Output is correct
34 Correct 1134 ms 396732 KB Output is correct
35 Correct 1127 ms 396932 KB Output is correct
36 Correct 1125 ms 396756 KB Output is correct
37 Correct 1491 ms 414884 KB Output is correct
38 Correct 1594 ms 414536 KB Output is correct
39 Correct 1514 ms 414772 KB Output is correct
40 Correct 1491 ms 407208 KB Output is correct
41 Correct 682 ms 335432 KB Output is correct
42 Correct 929 ms 346532 KB Output is correct
43 Correct 1772 ms 394528 KB Output is correct
44 Correct 1790 ms 395640 KB Output is correct
45 Correct 1008 ms 349668 KB Output is correct
46 Correct 934 ms 345484 KB Output is correct
47 Correct 2017 ms 389388 KB Output is correct
48 Correct 1551 ms 389780 KB Output is correct
49 Correct 292 ms 296424 KB Output is correct
50 Correct 293 ms 296196 KB Output is correct
51 Correct 287 ms 295516 KB Output is correct
52 Correct 290 ms 295112 KB Output is correct
53 Correct 296 ms 296564 KB Output is correct
54 Correct 312 ms 296580 KB Output is correct
55 Correct 293 ms 296452 KB Output is correct
56 Correct 295 ms 296456 KB Output is correct
57 Correct 305 ms 296388 KB Output is correct
58 Correct 325 ms 295448 KB Output is correct
59 Correct 289 ms 295992 KB Output is correct
60 Correct 300 ms 295296 KB Output is correct
61 Correct 3406 ms 485628 KB Output is correct
62 Execution timed out 5126 ms 597392 KB Time limit exceeded
63 Halted 0 ms 0 KB -