oj.uz

Submission #155614

# Submission time Handle Problem Language Result Execution time Memory
155614 2019-09-29T08:54:33 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 2590 ms 524080 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"0
#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];
int bio2[maxn][maxn], bio3[maxn][maxn];
set < array < int, 4 > > bio;

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[red[x][i].first][red[x][i].second]!=x+1){
			bio2[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[stup[i][x].first][stup[i][x].second]!=x+1){
			bio3[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);
	}
	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")
 
rect.cpp:4:18: warning: extra tokens at end of #include directive
 #include "rect.h"0
                  ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295160 KB Output is correct
2 Correct 292 ms 295884 KB Output is correct
3 Correct 352 ms 295744 KB Output is correct
4 Correct 303 ms 295828 KB Output is correct
5 Correct 290 ms 295452 KB Output is correct
6 Correct 289 ms 295672 KB Output is correct
7 Correct 288 ms 295544 KB Output is correct
8 Correct 305 ms 295420 KB Output is correct
9 Correct 292 ms 295672 KB Output is correct
10 Correct 301 ms 295800 KB Output is correct
11 Correct 302 ms 295644 KB Output is correct
12 Correct 289 ms 295800 KB Output is correct
13 Correct 346 ms 295032 KB Output is correct
14 Correct 335 ms 295136 KB Output is correct
15 Correct 333 ms 295108 KB Output is correct
16 Correct 303 ms 295140 KB Output is correct
17 Correct 288 ms 295036 KB Output is correct
18 Correct 289 ms 295132 KB Output is correct
19 Correct 289 ms 295672 KB Output is correct
20 Correct 329 ms 295416 KB Output is correct
21 Correct 289 ms 295288 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295160 KB Output is correct
2 Correct 292 ms 295884 KB Output is correct
3 Correct 352 ms 295744 KB Output is correct
4 Correct 303 ms 295828 KB Output is correct
5 Correct 290 ms 295452 KB Output is correct
6 Correct 289 ms 295672 KB Output is correct
7 Correct 288 ms 295544 KB Output is correct
8 Correct 305 ms 295420 KB Output is correct
9 Correct 292 ms 295672 KB Output is correct
10 Correct 301 ms 295800 KB Output is correct
11 Correct 302 ms 295644 KB Output is correct
12 Correct 289 ms 295800 KB Output is correct
13 Correct 346 ms 295032 KB Output is correct
14 Correct 335 ms 295136 KB Output is correct
15 Correct 333 ms 295108 KB Output is correct
16 Correct 303 ms 295140 KB Output is correct
17 Correct 294 ms 297364 KB Output is correct
18 Correct 320 ms 297344 KB Output is correct
19 Correct 288 ms 297352 KB Output is correct
20 Correct 293 ms 296948 KB Output is correct
21 Correct 292 ms 297108 KB Output is correct
22 Correct 304 ms 297192 KB Output is correct
23 Correct 292 ms 297080 KB Output is correct
24 Incorrect 293 ms 296636 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295160 KB Output is correct
2 Correct 292 ms 295884 KB Output is correct
3 Correct 352 ms 295744 KB Output is correct
4 Correct 303 ms 295828 KB Output is correct
5 Correct 290 ms 295452 KB Output is correct
6 Correct 289 ms 295672 KB Output is correct
7 Correct 288 ms 295544 KB Output is correct
8 Correct 305 ms 295420 KB Output is correct
9 Correct 292 ms 295672 KB Output is correct
10 Correct 301 ms 295800 KB Output is correct
11 Correct 302 ms 295644 KB Output is correct
12 Correct 289 ms 295800 KB Output is correct
13 Correct 346 ms 295032 KB Output is correct
14 Correct 335 ms 295136 KB Output is correct
15 Correct 333 ms 295108 KB Output is correct
16 Correct 303 ms 295140 KB Output is correct
17 Correct 294 ms 297364 KB Output is correct
18 Correct 320 ms 297344 KB Output is correct
19 Correct 288 ms 297352 KB Output is correct
20 Correct 293 ms 296948 KB Output is correct
21 Correct 292 ms 297108 KB Output is correct
22 Correct 304 ms 297192 KB Output is correct
23 Correct 292 ms 297080 KB Output is correct
24 Incorrect 293 ms 296636 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295160 KB Output is correct
2 Correct 292 ms 295884 KB Output is correct
3 Correct 352 ms 295744 KB Output is correct
4 Correct 303 ms 295828 KB Output is correct
5 Correct 290 ms 295452 KB Output is correct
6 Correct 289 ms 295672 KB Output is correct
7 Correct 288 ms 295544 KB Output is correct
8 Correct 305 ms 295420 KB Output is correct
9 Correct 292 ms 295672 KB Output is correct
10 Correct 301 ms 295800 KB Output is correct
11 Correct 302 ms 295644 KB Output is correct
12 Correct 289 ms 295800 KB Output is correct
13 Correct 346 ms 295032 KB Output is correct
14 Correct 335 ms 295136 KB Output is correct
15 Correct 333 ms 295108 KB Output is correct
16 Correct 303 ms 295140 KB Output is correct
17 Correct 294 ms 297364 KB Output is correct
18 Correct 320 ms 297344 KB Output is correct
19 Correct 288 ms 297352 KB Output is correct
20 Correct 293 ms 296948 KB Output is correct
21 Correct 292 ms 297108 KB Output is correct
22 Correct 304 ms 297192 KB Output is correct
23 Correct 292 ms 297080 KB Output is correct
24 Incorrect 293 ms 296636 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 305568 KB Output is correct
2 Correct 302 ms 304124 KB Output is correct
3 Correct 291 ms 295288 KB Output is correct
4 Correct 290 ms 295104 KB Output is correct
5 Correct 319 ms 304708 KB Output is correct
6 Correct 326 ms 304572 KB Output is correct
7 Correct 302 ms 304592 KB Output is correct
8 Correct 299 ms 303992 KB Output is correct
9 Correct 308 ms 303680 KB Output is correct
10 Correct 317 ms 300476 KB Output is correct
11 Correct 302 ms 303068 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 295208 KB Output is correct
2 Correct 1229 ms 409700 KB Output is correct
3 Correct 2406 ms 522500 KB Output is correct
4 Correct 2415 ms 524080 KB Output is correct
5 Correct 2590 ms 524012 KB Output is correct
6 Correct 556 ms 380436 KB Output is correct
7 Correct 878 ms 464260 KB Output is correct
8 Correct 883 ms 467324 KB Output is correct
9 Correct 288 ms 295036 KB Output is correct
10 Correct 289 ms 295132 KB Output is correct
11 Correct 289 ms 295672 KB Output is correct
12 Correct 329 ms 295416 KB Output is correct
13 Correct 289 ms 295288 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 295160 KB Output is correct
2 Correct 292 ms 295884 KB Output is correct
3 Correct 352 ms 295744 KB Output is correct
4 Correct 303 ms 295828 KB Output is correct
5 Correct 290 ms 295452 KB Output is correct
6 Correct 289 ms 295672 KB Output is correct
7 Correct 288 ms 295544 KB Output is correct
8 Correct 305 ms 295420 KB Output is correct
9 Correct 292 ms 295672 KB Output is correct
10 Correct 301 ms 295800 KB Output is correct
11 Correct 302 ms 295644 KB Output is correct
12 Correct 289 ms 295800 KB Output is correct
13 Correct 346 ms 295032 KB Output is correct
14 Correct 335 ms 295136 KB Output is correct
15 Correct 333 ms 295108 KB Output is correct
16 Correct 303 ms 295140 KB Output is correct
17 Correct 294 ms 297364 KB Output is correct
18 Correct 320 ms 297344 KB Output is correct
19 Correct 288 ms 297352 KB Output is correct
20 Correct 293 ms 296948 KB Output is correct
21 Correct 292 ms 297108 KB Output is correct
22 Correct 304 ms 297192 KB Output is correct
23 Correct 292 ms 297080 KB Output is correct
24 Incorrect 293 ms 296636 KB Output isn't correct