oj.uz

Submission #1066548

# Submission time Handle Problem Language Result Execution time Memory
1066548 2024-08-20T01:05:40 Z HD1 Rectangles (IOI19_rect) C++14
25 / 100
 598 ms 83284 KB 
#include "rect.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) int (s.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6;
ll n,m;
ll mxf[82][82][82], mxc[82][82][82];
vector< vector<int> > A;
void loco(vector<int> s, int x){//filas
	for(int i=1; i<m-1; i++){
		int mx=s[i];
		for(int j=i; j<m-1; j++){
			mx=max(mx,s[j]);
			mxf[x][i][j]=mx;
		}
	}
	return;
}
void loca(vector<int> s, int x){//columnas
	for(int i=1; i<n-1; i++){
		int mx=s[i];
		for(int j=i; j<n-1; j++){
			mx=max(mx,s[j]);
			mxc[x][i][j]=mx;
		}
	}
	return;
}
bool validf(int mx, int i, int l, int r){
	return A[i][l-1]>mx && A[i][r+1]>mx;
}
bool validc(int mx, int j, int l, int r){
	return A[l-1][j]>mx && A[r+1][j]>mx;
}
bool rectangle(int a, int b, int x, int y){
	bool good=true;
	for(int i=a; i<=x; i++){//por filas
		good&=validf(mxf[i][b][y], i, b, y);
	}
	for(int j=b; j<=y; j++){//por columnas
		good&=validc(mxc[j][a][x], j, a, x);
	}
	return good;
}
int fijo(int i1, int j1){
	int ans=0;
	for(int i=i1; i<n-1; i++){
		for(int j=j1; j<m-1; j++){
			if(rectangle(i1, j1, i, j)) ans++;
		}
	}
	return ans;
}
ll tmx(int k){
	int mx=0, ans=0;
	for(int i=k; i<m-1; i++){
		mx=max(mx,A[1][i]);
		if(A[1][i]<A[0][i] && A[1][i]<A[2][i]){
			if(mx<A[1][k-1] && mx<A[1][i+1])ans++;
		}
		else break;
	}
	return ans;
}
long long count_rectangles(vector< vector<int> > a) {
	A=a;
	n=sz(a);
	m=sz(a[0]);
	int ans=0;
	if(n<3)return ans;
	if(n==3){
		for(int i=1; i<m-1; i++){
			ans+=tmx(i);
			//cout<<i<<':'<<tmx(i)<<'\n';
		}
		//cout<<ans<<'\n';
		return ans;
	}
	for(int i=0; i<n; i++){
		loco(a[i], i);
	}
	vector<int> c;
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			c.pb(a[i][j]);
		}
		loca(c,j);
		c.clear();
	}
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			ans+=fijo(i,j);
		}
	}
	return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

3 10
1 2 4 5 6 3 6 7 4 8
8 1 9 2 1 1 1 1 1 9
9 7 5 7 5 9 9 4 3 8

1 1
1 1 2 1
1
1 1 1
1 1 2 1 6 1 1 1
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1624 KB Output is correct
4 Correct 4 ms 1624 KB Output is correct
5 Correct 3 ms 1624 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 1628 KB Output is correct
10 Correct 7 ms 1744 KB Output is correct
11 Correct 7 ms 1748 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 444 KB Output is correct
19 Correct 6 ms 1688 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1624 KB Output is correct
4 Correct 4 ms 1624 KB Output is correct
5 Correct 3 ms 1624 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 1628 KB Output is correct
10 Correct 7 ms 1744 KB Output is correct
11 Correct 7 ms 1748 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 444 KB Output is correct
19 Correct 6 ms 1688 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 598 ms 8948 KB Output is correct
23 Correct 572 ms 8792 KB Output is correct
24 Correct 580 ms 8796 KB Output is correct
25 Correct 470 ms 8796 KB Output is correct
26 Correct 491 ms 8888 KB Output is correct
27 Correct 492 ms 8792 KB Output is correct
28 Correct 513 ms 8796 KB Output is correct
29 Correct 128 ms 4696 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1624 KB Output is correct
4 Correct 4 ms 1624 KB Output is correct
5 Correct 3 ms 1624 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 1628 KB Output is correct
10 Correct 7 ms 1744 KB Output is correct
11 Correct 7 ms 1748 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 598 ms 8948 KB Output is correct
18 Correct 572 ms 8792 KB Output is correct
19 Correct 580 ms 8796 KB Output is correct
20 Correct 470 ms 8796 KB Output is correct
21 Correct 491 ms 8888 KB Output is correct
22 Correct 492 ms 8792 KB Output is correct
23 Correct 513 ms 8796 KB Output is correct
24 Correct 128 ms 4696 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 444 KB Output is correct
27 Correct 6 ms 1688 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Runtime error 7 ms 10332 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1624 KB Output is correct
4 Correct 4 ms 1624 KB Output is correct
5 Correct 3 ms 1624 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 1628 KB Output is correct
10 Correct 7 ms 1744 KB Output is correct
11 Correct 7 ms 1748 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 598 ms 8948 KB Output is correct
18 Correct 572 ms 8792 KB Output is correct
19 Correct 580 ms 8796 KB Output is correct
20 Correct 470 ms 8796 KB Output is correct
21 Correct 491 ms 8888 KB Output is correct
22 Correct 492 ms 8792 KB Output is correct
23 Correct 513 ms 8796 KB Output is correct
24 Correct 128 ms 4696 KB Output is correct
25 Runtime error 7 ms 10332 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 6 ms 1688 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Runtime error 187 ms 83284 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1624 KB Output is correct
4 Correct 4 ms 1624 KB Output is correct
5 Correct 3 ms 1624 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 7 ms 1628 KB Output is correct
10 Correct 7 ms 1744 KB Output is correct
11 Correct 7 ms 1748 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 598 ms 8948 KB Output is correct
18 Correct 572 ms 8792 KB Output is correct
19 Correct 580 ms 8796 KB Output is correct
20 Correct 470 ms 8796 KB Output is correct
21 Correct 491 ms 8888 KB Output is correct
22 Correct 492 ms 8792 KB Output is correct
23 Correct 513 ms 8796 KB Output is correct
24 Correct 128 ms 4696 KB Output is correct
25 Runtime error 7 ms 10332 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -