oj.uz

Submission #155622

# Submission time Handle Problem Language Result Execution time Memory
155622 2019-09-29T10:07:05 Z vanic Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 581040 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;
}
 
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(!bio4[hashiraj(red[x][i].first, red[x][i].second, x)]){
			if(bio2[hashiraj(red[x][i].first, red[x][i].second, x)]){
				printf("Sranje\n");
			}
			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));
	}
}
 
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(!bio5[hashiraj(stup[i][x].first, stup[i][x].second, x)]){
			if(bio3[hashiraj(stup[i][x].first, stup[i][x].second, x)]){
				printf("Sranje\n");
			}
			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));
	}
}
 
 
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);
		bio4.clear();
	}
	for(int i=0; i<m; i++){
		upd2(i);
		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 296 ms 299000 KB Output is correct
2 Correct 297 ms 299384 KB Output is correct
3 Correct 294 ms 299324 KB Output is correct
4 Correct 298 ms 299344 KB Output is correct
5 Correct 312 ms 299152 KB Output is correct
6 Correct 314 ms 299468 KB Output is correct
7 Correct 309 ms 299256 KB Output is correct
8 Correct 300 ms 299000 KB Output is correct
9 Correct 302 ms 299348 KB Output is correct
10 Correct 296 ms 299256 KB Output is correct
11 Correct 299 ms 299436 KB Output is correct
12 Correct 304 ms 299332 KB Output is correct
13 Correct 295 ms 298912 KB Output is correct
14 Correct 296 ms 299000 KB Output is correct
15 Correct 341 ms 298872 KB Output is correct
16 Correct 295 ms 298872 KB Output is correct
17 Correct 299 ms 298864 KB Output is correct
18 Correct 392 ms 298812 KB Output is correct
19 Correct 339 ms 299416 KB Output is correct
20 Correct 304 ms 299248 KB Output is correct
21 Correct 307 ms 298948 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 299000 KB Output is correct
2 Correct 297 ms 299384 KB Output is correct
3 Correct 294 ms 299324 KB Output is correct
4 Correct 298 ms 299344 KB Output is correct
5 Correct 312 ms 299152 KB Output is correct
6 Correct 314 ms 299468 KB Output is correct
7 Correct 309 ms 299256 KB Output is correct
8 Correct 300 ms 299000 KB Output is correct
9 Correct 302 ms 299348 KB Output is correct
10 Correct 296 ms 299256 KB Output is correct
11 Correct 299 ms 299436 KB Output is correct
12 Correct 304 ms 299332 KB Output is correct
13 Correct 295 ms 298912 KB Output is correct
14 Correct 296 ms 299000 KB Output is correct
15 Correct 341 ms 298872 KB Output is correct
16 Correct 295 ms 298872 KB Output is correct
17 Correct 306 ms 301176 KB Output is correct
18 Correct 321 ms 301192 KB Output is correct
19 Correct 313 ms 301304 KB Output is correct
20 Correct 300 ms 300384 KB Output is correct
21 Correct 305 ms 300908 KB Output is correct
22 Correct 316 ms 301000 KB Output is correct
23 Correct 319 ms 300892 KB Output is correct
24 Correct 361 ms 300408 KB Output is correct
25 Correct 299 ms 298864 KB Output is correct
26 Correct 392 ms 298812 KB Output is correct
27 Correct 339 ms 299416 KB Output is correct
28 Correct 304 ms 299248 KB Output is correct
29 Correct 307 ms 298948 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 299000 KB Output is correct
2 Correct 297 ms 299384 KB Output is correct
3 Correct 294 ms 299324 KB Output is correct
4 Correct 298 ms 299344 KB Output is correct
5 Correct 312 ms 299152 KB Output is correct
6 Correct 314 ms 299468 KB Output is correct
7 Correct 309 ms 299256 KB Output is correct
8 Correct 300 ms 299000 KB Output is correct
9 Correct 302 ms 299348 KB Output is correct
10 Correct 296 ms 299256 KB Output is correct
11 Correct 299 ms 299436 KB Output is correct
12 Correct 304 ms 299332 KB Output is correct
13 Correct 295 ms 298912 KB Output is correct
14 Correct 296 ms 299000 KB Output is correct
15 Correct 341 ms 298872 KB Output is correct
16 Correct 295 ms 298872 KB Output is correct
17 Correct 306 ms 301176 KB Output is correct
18 Correct 321 ms 301192 KB Output is correct
19 Correct 313 ms 301304 KB Output is correct
20 Correct 300 ms 300384 KB Output is correct
21 Correct 305 ms 300908 KB Output is correct
22 Correct 316 ms 301000 KB Output is correct
23 Correct 319 ms 300892 KB Output is correct
24 Correct 361 ms 300408 KB Output is correct
25 Correct 401 ms 310376 KB Output is correct
26 Correct 464 ms 310360 KB Output is correct
27 Correct 414 ms 310228 KB Output is correct
28 Correct 328 ms 304888 KB Output is correct
29 Correct 383 ms 308728 KB Output is correct
30 Correct 423 ms 308916 KB Output is correct
31 Correct 397 ms 308440 KB Output is correct
32 Correct 386 ms 308280 KB Output is correct
33 Correct 299 ms 298864 KB Output is correct
34 Correct 392 ms 298812 KB Output is correct
35 Correct 339 ms 299416 KB Output is correct
36 Correct 304 ms 299248 KB Output is correct
37 Correct 307 ms 298948 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 299000 KB Output is correct
2 Correct 297 ms 299384 KB Output is correct
3 Correct 294 ms 299324 KB Output is correct
4 Correct 298 ms 299344 KB Output is correct
5 Correct 312 ms 299152 KB Output is correct
6 Correct 314 ms 299468 KB Output is correct
7 Correct 309 ms 299256 KB Output is correct
8 Correct 300 ms 299000 KB Output is correct
9 Correct 302 ms 299348 KB Output is correct
10 Correct 296 ms 299256 KB Output is correct
11 Correct 299 ms 299436 KB Output is correct
12 Correct 304 ms 299332 KB Output is correct
13 Correct 295 ms 298912 KB Output is correct
14 Correct 296 ms 299000 KB Output is correct
15 Correct 341 ms 298872 KB Output is correct
16 Correct 295 ms 298872 KB Output is correct
17 Correct 306 ms 301176 KB Output is correct
18 Correct 321 ms 301192 KB Output is correct
19 Correct 313 ms 301304 KB Output is correct
20 Correct 300 ms 300384 KB Output is correct
21 Correct 305 ms 300908 KB Output is correct
22 Correct 316 ms 301000 KB Output is correct
23 Correct 319 ms 300892 KB Output is correct
24 Correct 361 ms 300408 KB Output is correct
25 Correct 401 ms 310376 KB Output is correct
26 Correct 464 ms 310360 KB Output is correct
27 Correct 414 ms 310228 KB Output is correct
28 Correct 328 ms 304888 KB Output is correct
29 Correct 383 ms 308728 KB Output is correct
30 Correct 423 ms 308916 KB Output is correct
31 Correct 397 ms 308440 KB Output is correct
32 Correct 386 ms 308280 KB Output is correct
33 Correct 1639 ms 400536 KB Output is correct
34 Correct 1445 ms 400624 KB Output is correct
35 Correct 1453 ms 400484 KB Output is correct
36 Correct 1548 ms 400616 KB Output is correct
37 Correct 1852 ms 418652 KB Output is correct
38 Correct 1916 ms 418388 KB Output is correct
39 Correct 1881 ms 418400 KB Output is correct
40 Correct 1954 ms 410760 KB Output is correct
41 Correct 665 ms 339012 KB Output is correct
42 Correct 935 ms 350328 KB Output is correct
43 Correct 2078 ms 398348 KB Output is correct
44 Correct 2283 ms 399364 KB Output is correct
45 Correct 1243 ms 353684 KB Output is correct
46 Correct 1144 ms 349508 KB Output is correct
47 Correct 1881 ms 393068 KB Output is correct
48 Correct 1873 ms 393312 KB Output is correct
49 Correct 299 ms 298864 KB Output is correct
50 Correct 392 ms 298812 KB Output is correct
51 Correct 339 ms 299416 KB Output is correct
52 Correct 304 ms 299248 KB Output is correct
53 Correct 307 ms 298948 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 300260 KB Output is correct
2 Correct 302 ms 300032 KB Output is correct
3 Correct 299 ms 299256 KB Output is correct
4 Correct 298 ms 298872 KB Output is correct
5 Correct 375 ms 300188 KB Output is correct
6 Correct 308 ms 300280 KB Output is correct
7 Correct 307 ms 300280 KB Output is correct
8 Correct 328 ms 300280 KB Output is correct
9 Correct 312 ms 300152 KB Output is correct
10 Correct 295 ms 299384 KB Output is correct
11 Correct 301 ms 299752 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 298928 KB Output is correct
2 Correct 3593 ms 489656 KB Output is correct
3 Execution timed out 5064 ms 581040 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 299000 KB Output is correct
2 Correct 297 ms 299384 KB Output is correct
3 Correct 294 ms 299324 KB Output is correct
4 Correct 298 ms 299344 KB Output is correct
5 Correct 312 ms 299152 KB Output is correct
6 Correct 314 ms 299468 KB Output is correct
7 Correct 309 ms 299256 KB Output is correct
8 Correct 300 ms 299000 KB Output is correct
9 Correct 302 ms 299348 KB Output is correct
10 Correct 296 ms 299256 KB Output is correct
11 Correct 299 ms 299436 KB Output is correct
12 Correct 304 ms 299332 KB Output is correct
13 Correct 295 ms 298912 KB Output is correct
14 Correct 296 ms 299000 KB Output is correct
15 Correct 341 ms 298872 KB Output is correct
16 Correct 295 ms 298872 KB Output is correct
17 Correct 306 ms 301176 KB Output is correct
18 Correct 321 ms 301192 KB Output is correct
19 Correct 313 ms 301304 KB Output is correct
20 Correct 300 ms 300384 KB Output is correct
21 Correct 305 ms 300908 KB Output is correct
22 Correct 316 ms 301000 KB Output is correct
23 Correct 319 ms 300892 KB Output is correct
24 Correct 361 ms 300408 KB Output is correct
25 Correct 401 ms 310376 KB Output is correct
26 Correct 464 ms 310360 KB Output is correct
27 Correct 414 ms 310228 KB Output is correct
28 Correct 328 ms 304888 KB Output is correct
29 Correct 383 ms 308728 KB Output is correct
30 Correct 423 ms 308916 KB Output is correct
31 Correct 397 ms 308440 KB Output is correct
32 Correct 386 ms 308280 KB Output is correct
33 Correct 1639 ms 400536 KB Output is correct
34 Correct 1445 ms 400624 KB Output is correct
35 Correct 1453 ms 400484 KB Output is correct
36 Correct 1548 ms 400616 KB Output is correct
37 Correct 1852 ms 418652 KB Output is correct
38 Correct 1916 ms 418388 KB Output is correct
39 Correct 1881 ms 418400 KB Output is correct
40 Correct 1954 ms 410760 KB Output is correct
41 Correct 665 ms 339012 KB Output is correct
42 Correct 935 ms 350328 KB Output is correct
43 Correct 2078 ms 398348 KB Output is correct
44 Correct 2283 ms 399364 KB Output is correct
45 Correct 1243 ms 353684 KB Output is correct
46 Correct 1144 ms 349508 KB Output is correct
47 Correct 1881 ms 393068 KB Output is correct
48 Correct 1873 ms 393312 KB Output is correct
49 Correct 301 ms 300260 KB Output is correct
50 Correct 302 ms 300032 KB Output is correct
51 Correct 299 ms 299256 KB Output is correct
52 Correct 298 ms 298872 KB Output is correct
53 Correct 375 ms 300188 KB Output is correct
54 Correct 308 ms 300280 KB Output is correct
55 Correct 307 ms 300280 KB Output is correct
56 Correct 328 ms 300280 KB Output is correct
57 Correct 312 ms 300152 KB Output is correct
58 Correct 295 ms 299384 KB Output is correct
59 Correct 301 ms 299752 KB Output is correct
60 Correct 308 ms 298928 KB Output is correct
61 Correct 3593 ms 489656 KB Output is correct
62 Execution timed out 5064 ms 581040 KB Time limit exceeded
63 Halted 0 ms 0 KB -