oj.uz

Submission #1066545

# Submission time Handle Problem Language Result Execution time Memory
1066545 2024-08-20T01:00:08 Z HD1 Rectangles (IOI19_rect) C++14
15 / 100
 571 ms 83112 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(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 1 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 1724 KB Output is correct
3 Correct 4 ms 1744 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1712 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 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 348 KB Output is correct
19 Correct 5 ms 1628 KB Output is correct
20 Correct 1 ms 1368 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 1724 KB Output is correct
3 Correct 4 ms 1744 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1712 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 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 348 KB Output is correct
19 Correct 5 ms 1628 KB Output is correct
20 Correct 1 ms 1368 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 566 ms 8796 KB Output is correct
23 Correct 571 ms 8796 KB Output is correct
24 Correct 567 ms 8796 KB Output is correct
25 Correct 473 ms 8796 KB Output is correct
26 Correct 492 ms 8792 KB Output is correct
27 Correct 485 ms 8900 KB Output is correct
28 Correct 495 ms 8796 KB Output is correct
29 Correct 105 ms 4840 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 1724 KB Output is correct
3 Correct 4 ms 1744 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1712 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 566 ms 8796 KB Output is correct
18 Correct 571 ms 8796 KB Output is correct
19 Correct 567 ms 8796 KB Output is correct
20 Correct 473 ms 8796 KB Output is correct
21 Correct 492 ms 8792 KB Output is correct
22 Correct 485 ms 8900 KB Output is correct
23 Correct 495 ms 8796 KB Output is correct
24 Correct 105 ms 4840 KB Output is correct
25 Correct 0 ms 348 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 1368 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 1724 KB Output is correct
3 Correct 4 ms 1744 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1712 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 566 ms 8796 KB Output is correct
18 Correct 571 ms 8796 KB Output is correct
19 Correct 567 ms 8796 KB Output is correct
20 Correct 473 ms 8796 KB Output is correct
21 Correct 492 ms 8792 KB Output is correct
22 Correct 485 ms 8900 KB Output is correct
23 Correct 495 ms 8796 KB Output is correct
24 Correct 105 ms 4840 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 600 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 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 348 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 1368 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Runtime error 185 ms 83112 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 1724 KB Output is correct
3 Correct 4 ms 1744 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1712 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 566 ms 8796 KB Output is correct
18 Correct 571 ms 8796 KB Output is correct
19 Correct 567 ms 8796 KB Output is correct
20 Correct 473 ms 8796 KB Output is correct
21 Correct 492 ms 8792 KB Output is correct
22 Correct 485 ms 8900 KB Output is correct
23 Correct 495 ms 8796 KB Output is correct
24 Correct 105 ms 4840 KB Output is correct
25 Runtime error 7 ms 10332 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -