oj.uz

Submission #197895

# Submission time Handle Problem Language Result Execution time Memory
197895 2020-01-24T04:20:17 Z arnold518 Rectangles (IOI19_rect) C++14
72 / 100
 5000 ms 540972 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2500;
 
int N, M, A[MAXN+10][MAXN+10];
int L[MAXN+10][MAXN+10], R[MAXN+10][MAXN+10], U[MAXN+10][MAXN+10], D[MAXN+10][MAXN+10];
 
struct Line
{
	int y, x1, x2;
	bool operator < (const Line &p) const
	{
		if(y!=p.y) return y<p.y;
		if(x1!=p.x1) return x1<p.x1;
		return x2<p.x2;
	}
 
	bool operator == (const Line &p) { return y==p.y && x1==p.x1 && x2==p.x2; }
	bool operator != (const Line &p) { return !(y==p.y && x1==p.x1 && x2==p.x2); }
};
 
vector<Line> H, V;
int lowH[MAXN*MAXN+10], lowV[MAXN*MAXN+10];
 
ll count_rectangles(vector<vector<int>> _A)
{
	int i, j;
 
	N=_A.size(); M=_A[0].size();
	for(i=1; i<=N; i++) for(j=1; j<=M; j++) A[i][j]=_A[i-1][j-1];
 
	for(i=1; i<=N; i++)
	{
		vector<int> S;
		S.clear();
		for(j=1; j<=M; j++) L[i][j]=0;
		for(j=1; j<=M; j++)
		{
			while(!S.empty() && A[i][S.back()]<=A[i][j]) S.pop_back();
			if(!S.empty()) L[i][j]=S.back();
			S.push_back(j);
		}
 
		S.clear();
		for(j=1; j<=M; j++) R[i][j]=M+1;
		for(j=M; j>=1; j--)
		{
			while(!S.empty() && A[i][S.back()]<=A[i][j]) S.pop_back();
			if(!S.empty()) R[i][j]=S.back();
			S.push_back(j);
		}
	}
	
	for(i=1; i<=M; i++)
	{
		vector<int> S;
		S.clear();
		for(j=1; j<=N; j++) U[j][i]=0;
		for(j=1; j<=N; j++)
		{
			while(!S.empty() && A[S.back()][i]<=A[j][i]) S.pop_back();
			if(!S.empty()) U[j][i]=S.back();
			S.push_back(j);
		}
 
		S.clear();
		for(j=1; j<=N; j++) D[j][i]=N+1;
		for(j=N; j>=1; j--)
		{
			while(!S.empty() && A[S.back()][i]<=A[j][i]) S.pop_back();
			if(!S.empty()) D[j][i]=S.back();
			S.push_back(j);
		}
	}
 
	for(i=1; i<=N; i++)
	{
		for(j=1; j<=M; j++)
		{
			if(L[i][j]==0) continue;
			if(R[i][j]==M+1) continue;
			H.push_back({i, L[i][j]+1, R[i][j]-1});
		}
		for(j=1; j<=M; j++)
		{
			if(U[i][j]==0) continue;
			if(D[i][j]==N+1) continue;
			V.push_back({j, U[i][j]+1, D[i][j]-1});
		}
	}
 
	sort(H.begin(), H.end());
	H.erase(unique(H.begin(), H.end()), H.end());
 
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
 
	for(i=H.size()-1, j=H.size()-1; i>=0; i--)
	{
		lowH[i]=H[i].y;
		Line t={H[i].y+1, H[i].x1, H[i].x2};
		for(; j>=0 && t<H[j]; j--);
		if(j>=0 && t==H[j]) lowH[i]=lowH[j];
	}
 
	for(i=V.size()-1, j=V.size()-1; i>=0; i--)
	{
		lowV[i]=V[i].y;
		Line t={V[i].y+1, V[i].x1, V[i].x2};
		for(; j>=0 && t<V[j]; j--);
		if(j>=0 && t==V[j]) lowV[i]=lowV[j];
	}
 
	vector<pair<pii, pii>> ans;
	for(i=2; i<=N-1; i++) for(j=2; j<=M-1; j++)
	{
		if(L[i][j]==0) continue;
		if(R[i][j]==M+1) continue;
		if(U[i][j]==0) continue;
		if(D[i][j]==N+1) continue;
 
		Line tu={U[i][j]+1, L[i][j]+1, R[i][j]-1};
		Line tl={L[i][j]+1, U[i][j]+1, D[i][j]-1};
 
		auto it=lower_bound(H.begin(), H.end(), tu);
		auto jt=lower_bound(V.begin(), V.end(), tl);
 		
 		if(it==H.end()) continue;
		if(*it!=tu) continue;
		if(jt==V.end()) continue;
		if(*jt!=tl) continue;
 
		if(lowH[it-H.begin()]<D[i][j]-1) continue;
		if(lowV[jt-V.begin()]<R[i][j]-1) continue;
 
		ans.push_back({pii(L[i][j]+1, R[i][j]-1), pii(U[i][j]+1, D[i][j]-1)});
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	return ans.size();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 1012 KB Output is correct
10 Correct 4 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 1016 KB Output is correct
20 Correct 3 ms 888 KB Output is correct
21 Correct 2 ms 504 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 1012 KB Output is correct
10 Correct 4 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 7 ms 2680 KB Output is correct
18 Correct 7 ms 2680 KB Output is correct
19 Correct 7 ms 2680 KB Output is correct
20 Correct 6 ms 2424 KB Output is correct
21 Correct 7 ms 2552 KB Output is correct
22 Correct 7 ms 2424 KB Output is correct
23 Correct 8 ms 2552 KB Output is correct
24 Correct 5 ms 2168 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 3 ms 1016 KB Output is correct
28 Correct 3 ms 888 KB Output is correct
29 Correct 2 ms 504 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 1012 KB Output is correct
10 Correct 4 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 7 ms 2680 KB Output is correct
18 Correct 7 ms 2680 KB Output is correct
19 Correct 7 ms 2680 KB Output is correct
20 Correct 6 ms 2424 KB Output is correct
21 Correct 7 ms 2552 KB Output is correct
22 Correct 7 ms 2424 KB Output is correct
23 Correct 8 ms 2552 KB Output is correct
24 Correct 5 ms 2168 KB Output is correct
25 Correct 34 ms 8528 KB Output is correct
26 Correct 34 ms 8552 KB Output is correct
27 Correct 33 ms 8556 KB Output is correct
28 Correct 25 ms 6516 KB Output is correct
29 Correct 37 ms 7272 KB Output is correct
30 Correct 36 ms 7376 KB Output is correct
31 Correct 34 ms 7720 KB Output is correct
32 Correct 33 ms 7336 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 3 ms 1016 KB Output is correct
36 Correct 3 ms 888 KB Output is correct
37 Correct 2 ms 504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 1012 KB Output is correct
10 Correct 4 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 7 ms 2680 KB Output is correct
18 Correct 7 ms 2680 KB Output is correct
19 Correct 7 ms 2680 KB Output is correct
20 Correct 6 ms 2424 KB Output is correct
21 Correct 7 ms 2552 KB Output is correct
22 Correct 7 ms 2424 KB Output is correct
23 Correct 8 ms 2552 KB Output is correct
24 Correct 5 ms 2168 KB Output is correct
25 Correct 34 ms 8528 KB Output is correct
26 Correct 34 ms 8552 KB Output is correct
27 Correct 33 ms 8556 KB Output is correct
28 Correct 25 ms 6516 KB Output is correct
29 Correct 37 ms 7272 KB Output is correct
30 Correct 36 ms 7376 KB Output is correct
31 Correct 34 ms 7720 KB Output is correct
32 Correct 33 ms 7336 KB Output is correct
33 Correct 120 ms 38848 KB Output is correct
34 Correct 133 ms 38740 KB Output is correct
35 Correct 122 ms 38948 KB Output is correct
36 Correct 119 ms 39012 KB Output is correct
37 Correct 443 ms 58740 KB Output is correct
38 Correct 453 ms 58896 KB Output is correct
39 Correct 437 ms 59088 KB Output is correct
40 Correct 408 ms 56132 KB Output is correct
41 Correct 210 ms 36496 KB Output is correct
42 Correct 275 ms 40008 KB Output is correct
43 Correct 455 ms 51492 KB Output is correct
44 Correct 459 ms 53380 KB Output is correct
45 Correct 226 ms 33908 KB Output is correct
46 Correct 212 ms 26892 KB Output is correct
47 Correct 447 ms 53400 KB Output is correct
48 Correct 447 ms 54188 KB Output is correct
49 Correct 2 ms 376 KB Output is correct
50 Correct 2 ms 376 KB Output is correct
51 Correct 3 ms 1016 KB Output is correct
52 Correct 3 ms 888 KB Output is correct
53 Correct 2 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Correct 4 ms 880 KB Output is correct
3 Correct 3 ms 636 KB Output is correct
4 Correct 0 ms 376 KB Output is correct
5 Correct 4 ms 888 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 4 ms 892 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 3 ms 760 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 1391 ms 134888 KB Output is correct
3 Correct 3330 ms 273980 KB Output is correct
4 Correct 3168 ms 275244 KB Output is correct
5 Correct 3119 ms 275324 KB Output is correct
6 Correct 319 ms 88824 KB Output is correct
7 Correct 771 ms 173308 KB Output is correct
8 Correct 751 ms 176376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 888 KB Output is correct
13 Correct 2 ms 504 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 7 ms 888 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 1012 KB Output is correct
10 Correct 4 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 1016 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 7 ms 2680 KB Output is correct
18 Correct 7 ms 2680 KB Output is correct
19 Correct 7 ms 2680 KB Output is correct
20 Correct 6 ms 2424 KB Output is correct
21 Correct 7 ms 2552 KB Output is correct
22 Correct 7 ms 2424 KB Output is correct
23 Correct 8 ms 2552 KB Output is correct
24 Correct 5 ms 2168 KB Output is correct
25 Correct 34 ms 8528 KB Output is correct
26 Correct 34 ms 8552 KB Output is correct
27 Correct 33 ms 8556 KB Output is correct
28 Correct 25 ms 6516 KB Output is correct
29 Correct 37 ms 7272 KB Output is correct
30 Correct 36 ms 7376 KB Output is correct
31 Correct 34 ms 7720 KB Output is correct
32 Correct 33 ms 7336 KB Output is correct
33 Correct 120 ms 38848 KB Output is correct
34 Correct 133 ms 38740 KB Output is correct
35 Correct 122 ms 38948 KB Output is correct
36 Correct 119 ms 39012 KB Output is correct
37 Correct 443 ms 58740 KB Output is correct
38 Correct 453 ms 58896 KB Output is correct
39 Correct 437 ms 59088 KB Output is correct
40 Correct 408 ms 56132 KB Output is correct
41 Correct 210 ms 36496 KB Output is correct
42 Correct 275 ms 40008 KB Output is correct
43 Correct 455 ms 51492 KB Output is correct
44 Correct 459 ms 53380 KB Output is correct
45 Correct 226 ms 33908 KB Output is correct
46 Correct 212 ms 26892 KB Output is correct
47 Correct 447 ms 53400 KB Output is correct
48 Correct 447 ms 54188 KB Output is correct
49 Correct 4 ms 1016 KB Output is correct
50 Correct 4 ms 880 KB Output is correct
51 Correct 3 ms 636 KB Output is correct
52 Correct 0 ms 376 KB Output is correct
53 Correct 4 ms 888 KB Output is correct
54 Correct 4 ms 888 KB Output is correct
55 Correct 4 ms 892 KB Output is correct
56 Correct 4 ms 760 KB Output is correct
57 Correct 4 ms 860 KB Output is correct
58 Correct 5 ms 504 KB Output is correct
59 Correct 3 ms 760 KB Output is correct
60 Correct 2 ms 632 KB Output is correct
61 Correct 1391 ms 134888 KB Output is correct
62 Correct 3330 ms 273980 KB Output is correct
63 Correct 3168 ms 275244 KB Output is correct
64 Correct 3119 ms 275324 KB Output is correct
65 Correct 319 ms 88824 KB Output is correct
66 Correct 771 ms 173308 KB Output is correct
67 Correct 751 ms 176376 KB Output is correct
68 Correct 1685 ms 290964 KB Output is correct
69 Correct 2552 ms 288912 KB Output is correct
70 Correct 1652 ms 289056 KB Output is correct
71 Correct 1648 ms 289040 KB Output is correct
72 Execution timed out 5118 ms 540972 KB Time limit exceeded
73 Halted 0 ms 0 KB -