oj.uz

Submission #155617

# Submission time Handle Problem Language Result Execution time Memory
155617 2019-09-29T09:07:18 Z vanic Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 562320 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 289 ms 295160 KB Output is correct
2 Correct 291 ms 295612 KB Output is correct
3 Correct 294 ms 295636 KB Output is correct
4 Correct 290 ms 295564 KB Output is correct
5 Correct 295 ms 295440 KB Output is correct
6 Correct 289 ms 295544 KB Output is correct
7 Correct 293 ms 295680 KB Output is correct
8 Correct 291 ms 295196 KB Output is correct
9 Correct 300 ms 295552 KB Output is correct
10 Correct 305 ms 295600 KB Output is correct
11 Correct 292 ms 295544 KB Output is correct
12 Correct 292 ms 295544 KB Output is correct
13 Correct 291 ms 295132 KB Output is correct
14 Correct 289 ms 295128 KB Output is correct
15 Correct 329 ms 295288 KB Output is correct
16 Correct 327 ms 295160 KB Output is correct
17 Correct 304 ms 295032 KB Output is correct
18 Correct 296 ms 295160 KB Output is correct
19 Correct 293 ms 295416 KB Output is correct
20 Correct 297 ms 295424 KB Output is correct
21 Correct 351 ms 295200 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295160 KB Output is correct
2 Correct 291 ms 295612 KB Output is correct
3 Correct 294 ms 295636 KB Output is correct
4 Correct 290 ms 295564 KB Output is correct
5 Correct 295 ms 295440 KB Output is correct
6 Correct 289 ms 295544 KB Output is correct
7 Correct 293 ms 295680 KB Output is correct
8 Correct 291 ms 295196 KB Output is correct
9 Correct 300 ms 295552 KB Output is correct
10 Correct 305 ms 295600 KB Output is correct
11 Correct 292 ms 295544 KB Output is correct
12 Correct 292 ms 295544 KB Output is correct
13 Correct 291 ms 295132 KB Output is correct
14 Correct 289 ms 295128 KB Output is correct
15 Correct 329 ms 295288 KB Output is correct
16 Correct 327 ms 295160 KB Output is correct
17 Correct 316 ms 297564 KB Output is correct
18 Correct 298 ms 297528 KB Output is correct
19 Correct 298 ms 297432 KB Output is correct
20 Correct 294 ms 296568 KB Output is correct
21 Correct 299 ms 297260 KB Output is correct
22 Correct 327 ms 297312 KB Output is correct
23 Correct 299 ms 297188 KB Output is correct
24 Correct 312 ms 296696 KB Output is correct
25 Correct 304 ms 295032 KB Output is correct
26 Correct 296 ms 295160 KB Output is correct
27 Correct 293 ms 295416 KB Output is correct
28 Correct 297 ms 295424 KB Output is correct
29 Correct 351 ms 295200 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295160 KB Output is correct
2 Correct 291 ms 295612 KB Output is correct
3 Correct 294 ms 295636 KB Output is correct
4 Correct 290 ms 295564 KB Output is correct
5 Correct 295 ms 295440 KB Output is correct
6 Correct 289 ms 295544 KB Output is correct
7 Correct 293 ms 295680 KB Output is correct
8 Correct 291 ms 295196 KB Output is correct
9 Correct 300 ms 295552 KB Output is correct
10 Correct 305 ms 295600 KB Output is correct
11 Correct 292 ms 295544 KB Output is correct
12 Correct 292 ms 295544 KB Output is correct
13 Correct 291 ms 295132 KB Output is correct
14 Correct 289 ms 295128 KB Output is correct
15 Correct 329 ms 295288 KB Output is correct
16 Correct 327 ms 295160 KB Output is correct
17 Correct 316 ms 297564 KB Output is correct
18 Correct 298 ms 297528 KB Output is correct
19 Correct 298 ms 297432 KB Output is correct
20 Correct 294 ms 296568 KB Output is correct
21 Correct 299 ms 297260 KB Output is correct
22 Correct 327 ms 297312 KB Output is correct
23 Correct 299 ms 297188 KB Output is correct
24 Correct 312 ms 296696 KB Output is correct
25 Correct 408 ms 306680 KB Output is correct
26 Correct 364 ms 306680 KB Output is correct
27 Correct 375 ms 306852 KB Output is correct
28 Correct 325 ms 301260 KB Output is correct
29 Correct 381 ms 305184 KB Output is correct
30 Correct 452 ms 305400 KB Output is correct
31 Correct 354 ms 304816 KB Output is correct
32 Correct 394 ms 304900 KB Output is correct
33 Correct 304 ms 295032 KB Output is correct
34 Correct 296 ms 295160 KB Output is correct
35 Correct 293 ms 295416 KB Output is correct
36 Correct 297 ms 295424 KB Output is correct
37 Correct 351 ms 295200 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295160 KB Output is correct
2 Correct 291 ms 295612 KB Output is correct
3 Correct 294 ms 295636 KB Output is correct
4 Correct 290 ms 295564 KB Output is correct
5 Correct 295 ms 295440 KB Output is correct
6 Correct 289 ms 295544 KB Output is correct
7 Correct 293 ms 295680 KB Output is correct
8 Correct 291 ms 295196 KB Output is correct
9 Correct 300 ms 295552 KB Output is correct
10 Correct 305 ms 295600 KB Output is correct
11 Correct 292 ms 295544 KB Output is correct
12 Correct 292 ms 295544 KB Output is correct
13 Correct 291 ms 295132 KB Output is correct
14 Correct 289 ms 295128 KB Output is correct
15 Correct 329 ms 295288 KB Output is correct
16 Correct 327 ms 295160 KB Output is correct
17 Correct 316 ms 297564 KB Output is correct
18 Correct 298 ms 297528 KB Output is correct
19 Correct 298 ms 297432 KB Output is correct
20 Correct 294 ms 296568 KB Output is correct
21 Correct 299 ms 297260 KB Output is correct
22 Correct 327 ms 297312 KB Output is correct
23 Correct 299 ms 297188 KB Output is correct
24 Correct 312 ms 296696 KB Output is correct
25 Correct 408 ms 306680 KB Output is correct
26 Correct 364 ms 306680 KB Output is correct
27 Correct 375 ms 306852 KB Output is correct
28 Correct 325 ms 301260 KB Output is correct
29 Correct 381 ms 305184 KB Output is correct
30 Correct 452 ms 305400 KB Output is correct
31 Correct 354 ms 304816 KB Output is correct
32 Correct 394 ms 304900 KB Output is correct
33 Correct 1302 ms 397428 KB Output is correct
34 Correct 1151 ms 397320 KB Output is correct
35 Correct 1140 ms 396992 KB Output is correct
36 Correct 1143 ms 397208 KB Output is correct
37 Correct 1488 ms 415072 KB Output is correct
38 Correct 1556 ms 415012 KB Output is correct
39 Correct 1540 ms 415252 KB Output is correct
40 Correct 1489 ms 407304 KB Output is correct
41 Correct 740 ms 335616 KB Output is correct
42 Correct 841 ms 346904 KB Output is correct
43 Correct 1997 ms 395044 KB Output is correct
44 Correct 1683 ms 396100 KB Output is correct
45 Correct 886 ms 350280 KB Output is correct
46 Correct 1004 ms 345884 KB Output is correct
47 Correct 1594 ms 389888 KB Output is correct
48 Correct 1615 ms 390092 KB Output is correct
49 Correct 304 ms 295032 KB Output is correct
50 Correct 296 ms 295160 KB Output is correct
51 Correct 293 ms 295416 KB Output is correct
52 Correct 297 ms 295424 KB Output is correct
53 Correct 351 ms 295200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 296504 KB Output is correct
2 Correct 304 ms 296240 KB Output is correct
3 Correct 331 ms 295544 KB Output is correct
4 Correct 290 ms 295032 KB Output is correct
5 Correct 351 ms 296440 KB Output is correct
6 Correct 327 ms 296452 KB Output is correct
7 Correct 305 ms 296492 KB Output is correct
8 Correct 315 ms 296392 KB Output is correct
9 Correct 301 ms 296312 KB Output is correct
10 Correct 296 ms 295544 KB Output is correct
11 Correct 308 ms 296056 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 295156 KB Output is correct
2 Correct 3542 ms 485752 KB Output is correct
3 Execution timed out 5062 ms 562320 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 295160 KB Output is correct
2 Correct 291 ms 295612 KB Output is correct
3 Correct 294 ms 295636 KB Output is correct
4 Correct 290 ms 295564 KB Output is correct
5 Correct 295 ms 295440 KB Output is correct
6 Correct 289 ms 295544 KB Output is correct
7 Correct 293 ms 295680 KB Output is correct
8 Correct 291 ms 295196 KB Output is correct
9 Correct 300 ms 295552 KB Output is correct
10 Correct 305 ms 295600 KB Output is correct
11 Correct 292 ms 295544 KB Output is correct
12 Correct 292 ms 295544 KB Output is correct
13 Correct 291 ms 295132 KB Output is correct
14 Correct 289 ms 295128 KB Output is correct
15 Correct 329 ms 295288 KB Output is correct
16 Correct 327 ms 295160 KB Output is correct
17 Correct 316 ms 297564 KB Output is correct
18 Correct 298 ms 297528 KB Output is correct
19 Correct 298 ms 297432 KB Output is correct
20 Correct 294 ms 296568 KB Output is correct
21 Correct 299 ms 297260 KB Output is correct
22 Correct 327 ms 297312 KB Output is correct
23 Correct 299 ms 297188 KB Output is correct
24 Correct 312 ms 296696 KB Output is correct
25 Correct 408 ms 306680 KB Output is correct
26 Correct 364 ms 306680 KB Output is correct
27 Correct 375 ms 306852 KB Output is correct
28 Correct 325 ms 301260 KB Output is correct
29 Correct 381 ms 305184 KB Output is correct
30 Correct 452 ms 305400 KB Output is correct
31 Correct 354 ms 304816 KB Output is correct
32 Correct 394 ms 304900 KB Output is correct
33 Correct 1302 ms 397428 KB Output is correct
34 Correct 1151 ms 397320 KB Output is correct
35 Correct 1140 ms 396992 KB Output is correct
36 Correct 1143 ms 397208 KB Output is correct
37 Correct 1488 ms 415072 KB Output is correct
38 Correct 1556 ms 415012 KB Output is correct
39 Correct 1540 ms 415252 KB Output is correct
40 Correct 1489 ms 407304 KB Output is correct
41 Correct 740 ms 335616 KB Output is correct
42 Correct 841 ms 346904 KB Output is correct
43 Correct 1997 ms 395044 KB Output is correct
44 Correct 1683 ms 396100 KB Output is correct
45 Correct 886 ms 350280 KB Output is correct
46 Correct 1004 ms 345884 KB Output is correct
47 Correct 1594 ms 389888 KB Output is correct
48 Correct 1615 ms 390092 KB Output is correct
49 Correct 324 ms 296504 KB Output is correct
50 Correct 304 ms 296240 KB Output is correct
51 Correct 331 ms 295544 KB Output is correct
52 Correct 290 ms 295032 KB Output is correct
53 Correct 351 ms 296440 KB Output is correct
54 Correct 327 ms 296452 KB Output is correct
55 Correct 305 ms 296492 KB Output is correct
56 Correct 315 ms 296392 KB Output is correct
57 Correct 301 ms 296312 KB Output is correct
58 Correct 296 ms 295544 KB Output is correct
59 Correct 308 ms 296056 KB Output is correct
60 Correct 295 ms 295156 KB Output is correct
61 Correct 3542 ms 485752 KB Output is correct
62 Execution timed out 5062 ms 562320 KB Time limit exceeded
63 Halted 0 ms 0 KB -