oj.uz

Submission #1066555

# Submission time Handle Problem Language Result Execution time Memory
1066555 2024-08-20T01:15:20 Z HD1 Rectangles (IOI19_rect) C++14
25 / 100
 5000 ms 221588 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[210][210][210], mxc[210][210][210];
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 5 ms 3400 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Correct 5 ms 3404 KB Output is correct
5 Correct 4 ms 3404 KB Output is correct
6 Correct 7 ms 3404 KB Output is correct
7 Correct 2 ms 1624 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 8 ms 3164 KB Output is correct
10 Correct 8 ms 3160 KB Output is correct
11 Correct 8 ms 3164 KB Output is correct
12 Correct 6 ms 3420 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 348 KB Output is correct
19 Correct 5 ms 3404 KB Output is correct
20 Correct 1 ms 1928 KB Output is correct
21 Correct 0 ms 344 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 5 ms 3400 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Correct 5 ms 3404 KB Output is correct
5 Correct 4 ms 3404 KB Output is correct
6 Correct 7 ms 3404 KB Output is correct
7 Correct 2 ms 1624 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 8 ms 3164 KB Output is correct
10 Correct 8 ms 3160 KB Output is correct
11 Correct 8 ms 3164 KB Output is correct
12 Correct 6 ms 3420 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 348 KB Output is correct
19 Correct 5 ms 3404 KB Output is correct
20 Correct 1 ms 1928 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 567 ms 21592 KB Output is correct
23 Correct 578 ms 21592 KB Output is correct
24 Correct 602 ms 21596 KB Output is correct
25 Correct 483 ms 21560 KB Output is correct
26 Correct 492 ms 21084 KB Output is correct
27 Correct 496 ms 21592 KB Output is correct
28 Correct 497 ms 21596 KB Output is correct
29 Correct 104 ms 11020 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 5 ms 3400 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Correct 5 ms 3404 KB Output is correct
5 Correct 4 ms 3404 KB Output is correct
6 Correct 7 ms 3404 KB Output is correct
7 Correct 2 ms 1624 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 8 ms 3164 KB Output is correct
10 Correct 8 ms 3160 KB Output is correct
11 Correct 8 ms 3164 KB Output is correct
12 Correct 6 ms 3420 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 567 ms 21592 KB Output is correct
18 Correct 578 ms 21592 KB Output is correct
19 Correct 602 ms 21596 KB Output is correct
20 Correct 483 ms 21560 KB Output is correct
21 Correct 492 ms 21084 KB Output is correct
22 Correct 496 ms 21592 KB Output is correct
23 Correct 497 ms 21596 KB Output is correct
24 Correct 104 ms 11020 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 3404 KB Output is correct
28 Correct 1 ms 1928 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Execution timed out 5078 ms 132876 KB Time limit exceeded
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 5 ms 3400 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Correct 5 ms 3404 KB Output is correct
5 Correct 4 ms 3404 KB Output is correct
6 Correct 7 ms 3404 KB Output is correct
7 Correct 2 ms 1624 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 8 ms 3164 KB Output is correct
10 Correct 8 ms 3160 KB Output is correct
11 Correct 8 ms 3164 KB Output is correct
12 Correct 6 ms 3420 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 567 ms 21592 KB Output is correct
18 Correct 578 ms 21592 KB Output is correct
19 Correct 602 ms 21596 KB Output is correct
20 Correct 483 ms 21560 KB Output is correct
21 Correct 492 ms 21084 KB Output is correct
22 Correct 496 ms 21592 KB Output is correct
23 Correct 497 ms 21596 KB Output is correct
24 Correct 104 ms 11020 KB Output is correct
25 Execution timed out 5078 ms 132876 KB Time limit exceeded
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 348 KB Output is correct
3 Correct 0 ms 556 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 536 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 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 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 348 KB Output is correct
3 Correct 5 ms 3404 KB Output is correct
4 Correct 1 ms 1928 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Runtime error 562 ms 221588 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 5 ms 3400 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Correct 5 ms 3404 KB Output is correct
5 Correct 4 ms 3404 KB Output is correct
6 Correct 7 ms 3404 KB Output is correct
7 Correct 2 ms 1624 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 8 ms 3164 KB Output is correct
10 Correct 8 ms 3160 KB Output is correct
11 Correct 8 ms 3164 KB Output is correct
12 Correct 6 ms 3420 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 567 ms 21592 KB Output is correct
18 Correct 578 ms 21592 KB Output is correct
19 Correct 602 ms 21596 KB Output is correct
20 Correct 483 ms 21560 KB Output is correct
21 Correct 492 ms 21084 KB Output is correct
22 Correct 496 ms 21592 KB Output is correct
23 Correct 497 ms 21596 KB Output is correct
24 Correct 104 ms 11020 KB Output is correct
25 Execution timed out 5078 ms 132876 KB Time limit exceeded
26 Halted 0 ms 0 KB -