oj.uz

Submission #1066542

# Submission time Handle Problem Language Result Execution time Memory
1066542 2024-08-20T00:55:59 Z HD1 Rectangles (IOI19_rect) C++14
15 / 100
 582 ms 83332 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][k]);
		if(mx<A[1][k-1] && A[1][i]<A[2][i] && A[1][i]<A[0][i] && mx< A[1][i+1])ans++;
		if(A[1][i]>=A[2][i] || A[1][i]>=A[0][i])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 1 2 1 6 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 344 KB Output is correct
2 Correct 5 ms 1624 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 6 ms 1748 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 7 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 440 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 5 ms 1628 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 344 KB Output is correct
2 Correct 5 ms 1624 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 6 ms 1748 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 7 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 440 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 5 ms 1628 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 582 ms 8796 KB Output is correct
23 Correct 569 ms 8968 KB Output is correct
24 Correct 573 ms 8956 KB Output is correct
25 Correct 465 ms 8796 KB Output is correct
26 Correct 503 ms 8792 KB Output is correct
27 Correct 504 ms 8904 KB Output is correct
28 Correct 512 ms 8940 KB Output is correct
29 Correct 107 ms 4820 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 5 ms 1624 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 6 ms 1748 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 7 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 582 ms 8796 KB Output is correct
18 Correct 569 ms 8968 KB Output is correct
19 Correct 573 ms 8956 KB Output is correct
20 Correct 465 ms 8796 KB Output is correct
21 Correct 503 ms 8792 KB Output is correct
22 Correct 504 ms 8904 KB Output is correct
23 Correct 512 ms 8940 KB Output is correct
24 Correct 107 ms 4820 KB Output is correct
25 Correct 0 ms 440 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 5 ms 1628 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 344 KB Output is correct
2 Correct 5 ms 1624 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 6 ms 1748 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 7 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 582 ms 8796 KB Output is correct
18 Correct 569 ms 8968 KB Output is correct
19 Correct 573 ms 8956 KB Output is correct
20 Correct 465 ms 8796 KB Output is correct
21 Correct 503 ms 8792 KB Output is correct
22 Correct 504 ms 8904 KB Output is correct
23 Correct 512 ms 8940 KB Output is correct
24 Correct 107 ms 4820 KB Output is correct
25 Runtime error 7 ms 10332 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 0 ms 428 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 448 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 1628 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 856 KB Output is correct
7 Runtime error 181 ms 83332 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 344 KB Output is correct
2 Correct 5 ms 1624 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 4 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1748 KB Output is correct
10 Correct 6 ms 1748 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 7 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 582 ms 8796 KB Output is correct
18 Correct 569 ms 8968 KB Output is correct
19 Correct 573 ms 8956 KB Output is correct
20 Correct 465 ms 8796 KB Output is correct
21 Correct 503 ms 8792 KB Output is correct
22 Correct 504 ms 8904 KB Output is correct
23 Correct 512 ms 8940 KB Output is correct
24 Correct 107 ms 4820 KB Output is correct
25 Runtime error 7 ms 10332 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -