oj.uz

Submission #155788

# Submission time Handle Problem Language Result Execution time Memory
155788 2019-09-30T15:02:32 Z vanic Rectangles (IOI19_rect) C++14
31 / 100
 2451 ms 528148 KB 
#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];
int bio2[maxn][maxn], bio3[maxn][maxn];
vector < 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[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, vector < int > &l){
	int lo=0, hi=l.size(), mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		if(l[mid]<x){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
	}
	return lo;
}
 
void 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;
	}
	int pos1=binary(c1, r[r1][r2]);
	int pos2=binary(r1, c[c1][c2]);
	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){
		bio.push_back({r1, r2, c1, c2});
	}
}
 
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);
	}
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			provjeri(i, j);
		}
	}
	sort(bio.begin(), bio.end());
	bio.erase(unique(bio.begin(), bio.end()), bio.end());
	return bio.size();
}
 
/*
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);
	}
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			provjeri(i, j);
		}
	}
	sort(bio.begin(), bio.end());
	bio.erase(unique(bio.begin(), bio.end()), bio.end());
	printf("%d\n", bio.size());
	return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 299000 KB Output is correct
2 Correct 272 ms 299640 KB Output is correct
3 Correct 272 ms 299460 KB Output is correct
4 Correct 287 ms 299512 KB Output is correct
5 Correct 273 ms 299256 KB Output is correct
6 Correct 272 ms 299512 KB Output is correct
7 Correct 271 ms 299384 KB Output is correct
8 Correct 288 ms 299356 KB Output is correct
9 Correct 273 ms 299624 KB Output is correct
10 Correct 284 ms 299640 KB Output is correct
11 Correct 293 ms 299512 KB Output is correct
12 Correct 297 ms 299576 KB Output is correct
13 Correct 287 ms 298872 KB Output is correct
14 Correct 275 ms 299000 KB Output is correct
15 Correct 273 ms 298904 KB Output is correct
16 Correct 272 ms 298948 KB Output is correct
17 Correct 275 ms 298916 KB Output is correct
18 Correct 274 ms 298872 KB Output is correct
19 Correct 273 ms 299384 KB Output is correct
20 Correct 272 ms 299348 KB Output is correct
21 Correct 272 ms 298976 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 299000 KB Output is correct
2 Correct 272 ms 299640 KB Output is correct
3 Correct 272 ms 299460 KB Output is correct
4 Correct 287 ms 299512 KB Output is correct
5 Correct 273 ms 299256 KB Output is correct
6 Correct 272 ms 299512 KB Output is correct
7 Correct 271 ms 299384 KB Output is correct
8 Correct 288 ms 299356 KB Output is correct
9 Correct 273 ms 299624 KB Output is correct
10 Correct 284 ms 299640 KB Output is correct
11 Correct 293 ms 299512 KB Output is correct
12 Correct 297 ms 299576 KB Output is correct
13 Correct 287 ms 298872 KB Output is correct
14 Correct 275 ms 299000 KB Output is correct
15 Correct 273 ms 298904 KB Output is correct
16 Correct 272 ms 298948 KB Output is correct
17 Correct 276 ms 300920 KB Output is correct
18 Correct 279 ms 300944 KB Output is correct
19 Correct 278 ms 300924 KB Output is correct
20 Correct 294 ms 300920 KB Output is correct
21 Correct 281 ms 300864 KB Output is correct
22 Correct 284 ms 300876 KB Output is correct
23 Correct 277 ms 300908 KB Output is correct
24 Incorrect 275 ms 300508 KB Output isn't correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 299000 KB Output is correct
2 Correct 272 ms 299640 KB Output is correct
3 Correct 272 ms 299460 KB Output is correct
4 Correct 287 ms 299512 KB Output is correct
5 Correct 273 ms 299256 KB Output is correct
6 Correct 272 ms 299512 KB Output is correct
7 Correct 271 ms 299384 KB Output is correct
8 Correct 288 ms 299356 KB Output is correct
9 Correct 273 ms 299624 KB Output is correct
10 Correct 284 ms 299640 KB Output is correct
11 Correct 293 ms 299512 KB Output is correct
12 Correct 297 ms 299576 KB Output is correct
13 Correct 287 ms 298872 KB Output is correct
14 Correct 275 ms 299000 KB Output is correct
15 Correct 273 ms 298904 KB Output is correct
16 Correct 272 ms 298948 KB Output is correct
17 Correct 276 ms 300920 KB Output is correct
18 Correct 279 ms 300944 KB Output is correct
19 Correct 278 ms 300924 KB Output is correct
20 Correct 294 ms 300920 KB Output is correct
21 Correct 281 ms 300864 KB Output is correct
22 Correct 284 ms 300876 KB Output is correct
23 Correct 277 ms 300908 KB Output is correct
24 Incorrect 275 ms 300508 KB Output isn't correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 299000 KB Output is correct
2 Correct 272 ms 299640 KB Output is correct
3 Correct 272 ms 299460 KB Output is correct
4 Correct 287 ms 299512 KB Output is correct
5 Correct 273 ms 299256 KB Output is correct
6 Correct 272 ms 299512 KB Output is correct
7 Correct 271 ms 299384 KB Output is correct
8 Correct 288 ms 299356 KB Output is correct
9 Correct 273 ms 299624 KB Output is correct
10 Correct 284 ms 299640 KB Output is correct
11 Correct 293 ms 299512 KB Output is correct
12 Correct 297 ms 299576 KB Output is correct
13 Correct 287 ms 298872 KB Output is correct
14 Correct 275 ms 299000 KB Output is correct
15 Correct 273 ms 298904 KB Output is correct
16 Correct 272 ms 298948 KB Output is correct
17 Correct 276 ms 300920 KB Output is correct
18 Correct 279 ms 300944 KB Output is correct
19 Correct 278 ms 300924 KB Output is correct
20 Correct 294 ms 300920 KB Output is correct
21 Correct 281 ms 300864 KB Output is correct
22 Correct 284 ms 300876 KB Output is correct
23 Correct 277 ms 300908 KB Output is correct
24 Incorrect 275 ms 300508 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 309244 KB Output is correct
2 Correct 283 ms 307832 KB Output is correct
3 Correct 275 ms 299060 KB Output is correct
4 Correct 278 ms 298872 KB Output is correct
5 Correct 284 ms 308524 KB Output is correct
6 Correct 284 ms 308216 KB Output is correct
7 Correct 319 ms 308252 KB Output is correct
8 Correct 339 ms 307708 KB Output is correct
9 Correct 343 ms 307412 KB Output is correct
10 Correct 334 ms 304148 KB Output is correct
11 Correct 342 ms 306808 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 299024 KB Output is correct
2 Correct 1195 ms 411168 KB Output is correct
3 Correct 2300 ms 526812 KB Output is correct
4 Correct 2342 ms 527984 KB Output is correct
5 Correct 2451 ms 528148 KB Output is correct
6 Correct 629 ms 390108 KB Output is correct
7 Correct 1046 ms 475732 KB Output is correct
8 Correct 1006 ms 478816 KB Output is correct
9 Correct 275 ms 298916 KB Output is correct
10 Correct 274 ms 298872 KB Output is correct
11 Correct 273 ms 299384 KB Output is correct
12 Correct 272 ms 299348 KB Output is correct
13 Correct 272 ms 298976 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 299000 KB Output is correct
2 Correct 272 ms 299640 KB Output is correct
3 Correct 272 ms 299460 KB Output is correct
4 Correct 287 ms 299512 KB Output is correct
5 Correct 273 ms 299256 KB Output is correct
6 Correct 272 ms 299512 KB Output is correct
7 Correct 271 ms 299384 KB Output is correct
8 Correct 288 ms 299356 KB Output is correct
9 Correct 273 ms 299624 KB Output is correct
10 Correct 284 ms 299640 KB Output is correct
11 Correct 293 ms 299512 KB Output is correct
12 Correct 297 ms 299576 KB Output is correct
13 Correct 287 ms 298872 KB Output is correct
14 Correct 275 ms 299000 KB Output is correct
15 Correct 273 ms 298904 KB Output is correct
16 Correct 272 ms 298948 KB Output is correct
17 Correct 276 ms 300920 KB Output is correct
18 Correct 279 ms 300944 KB Output is correct
19 Correct 278 ms 300924 KB Output is correct
20 Correct 294 ms 300920 KB Output is correct
21 Correct 281 ms 300864 KB Output is correct
22 Correct 284 ms 300876 KB Output is correct
23 Correct 277 ms 300908 KB Output is correct
24 Incorrect 275 ms 300508 KB Output isn't correct