oj.uz

Submission #154202

# Submission time Handle Problem Language Result Execution time Memory
154202 2019-09-18T23:39:20 Z wilwxk Rectangles (IOI19_rect) C++14
49 / 100
 2778 ms 145272 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=705;
const int INF=1e9+9;
vector<vector<int> > v;
int borda[4][MAXN][MAXN]; // xl, xr, yl, yr
int seg[4][MAXN*4][MAXN*4];
int n, m, respf;

struct cara {
	int i, j;
	bool operator<(cara _) const {
		return v[i][j]<v[_.i][_.j];
	}
};
vector<cara> lista;

void histogrami() {
	stack<pair<int, int> > st;
	for(int i=0; i<n; i++) {
		while(st.size()) st.pop(); st.push({INF, -1});
		for(int j=0; j<m; j++) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[0][i+1][j+1]=st.top().second+1;
			st.push({v[i][j], j});
		}
		while(st.size()) st.pop(); st.push({INF, m});
		for(int j=m-1; j>=0; j--) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[1][i+1][j+1]=st.top().second-1;
			st.push({v[i][j], j});
		}
	}
}
void histogramj() {
	stack<pair<int, int> > st;
	for(int j=0; j<m; j++) {
		while(st.size()) st.pop(); st.push({INF, -1});
		for(int i=0; i<n; i++) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[2][i+1][j+1]=st.top().second+1;
			st.push({v[i][j], i});
		}
		while(st.size()) st.pop(); st.push({INF, n});
		for(int i=n-1; i>=0; i--) {
			while(st.top().first<=v[i][j]) st.pop();
			borda[3][i+1][j+1]=st.top().second-1;
			st.push({v[i][j], i});
		}
	}
}

void remergej(int ssind, int sind) {
	for(int i=0; i<4; i++) {
		if(i&1) seg[i][ssind][sind]=max(seg[i][ssind][sind*2], seg[i][ssind][sind*2+1]);
		else seg[i][ssind][sind]=min(seg[i][ssind][sind*2], seg[i][ssind][sind*2+1]);
	}
}
void remergei(int ssind, int sind, int ini, int fim, int xind) {
	for(int i=0; i<4; i++) {
		if(i&1) seg[i][ssind][sind]=max(seg[i][ssind*2][sind], seg[i][ssind*2+1][sind]);
		else seg[i][ssind][sind]=min(seg[i][ssind*2][sind], seg[i][ssind*2+1][sind]);
	}
	if(ini==fim) return;
	int mid=(ini+fim)/2;
	if(xind<=mid) remergei(ssind, sind*2, ini, mid, xind);
	else remergei(ssind, sind*2+1, mid+1, fim, xind);
}

void updj(int ssind, int yind, int sind, int ini, int fim, int xind) {
	if(ini==fim) {
		for(int i=0; i<4; i++) seg[i][ssind][sind]=borda[i][yind][xind];
		return;
	}
	int mid=(ini+fim)/2;
	if(xind<=mid) updj(ssind, yind, sind*2, ini, mid, xind);
	else updj(ssind, yind, sind*2+1, mid+1, fim, xind);
	remergej(ssind, sind);
}
void updi(int sind, int ini, int fim, int yind, int xind) {
	if(ini==fim) {
		updj(sind, yind, 1, 1, m, xind);
		return;
	}
	int mid=(ini+fim)/2;
	if(yind<=mid) updi(sind*2, ini, mid, yind, xind);
	else updi(sind*2+1, mid+1, fim, yind, xind);
	remergei(sind, 1, 1, m, xind);
}

void quj(int ssind, int sind, int ini, int fim, int xl, int xr) {
	if(xl<=ini&&xr>=fim) {
		for(int k=0; k<4; k++) {
			if(k&1) seg[k][0][0]=max(seg[k][0][0], seg[k][ssind][sind]);
			else seg[k][0][0]=min(seg[k][0][0], seg[k][ssind][sind]);
		}
		return;
	}
	int mid=(ini+fim)/2;
	if(xl<=mid) quj(ssind, sind*2, ini, mid, xl, xr);
	if(xr>mid) quj(ssind, sind*2+1, mid+1, fim, xl, xr);
}
void qui(int sind, int ini, int fim, int xl, int xr, int yl, int yr) {
	if(yl<=ini&&yr>=fim) {
		quj(sind, 1, 1, m, xl, xr);
		return;
	}
	int mid=(ini+fim)/2;
	if(yl<=mid) qui(sind*2, ini, mid, xl, xr, yl, yr);
	if(yr>mid) qui(sind*2+1, mid+1, fim, xl, xr, yl, yr);
}

ll count_rectangles(vector< vector<int> > A) {
	v=A; n=A.size(); m=A[0].size();
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cara cur;
			cur.i=i; cur.j=j;
			lista.push_back(cur);
		}
	}
	histogrami();
	histogramj();
	for(int k=0; k<4; k++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) borda[k][i][j]++;
	
	//1-indexed now
	// for(auto cur : lista) printf("(%d, %d): %d %d // %d %d\n", cur.i, cur.j, cur.xl, cur.xr, cur.yl, cur.yr);

	for(int i=0; i<4*n; i++) {
		for(int j=0; j<4*m; j++) {
			seg[0][i][j]=seg[2][i][j]=-1;
			seg[1][i][j]=seg[3][i][j]=MAXN;
		}
	}

	sort(lista.begin(), lista.end());
	for(auto cur : lista) {
		int i=cur.i+1; int j=cur.j+1;
		updi(1, 1, n, i, j);
		if(borda[0][i][j]<=1||borda[1][i][j]>=m||borda[2][i][j]<=1||borda[3][i][j]>=n) continue;
		bool ok=1;
		seg[0][0][0]=seg[2][0][0]=MAXN;
		seg[1][0][0]=seg[3][0][0]=-1;
		qui(1, 1, n, borda[0][i][j], borda[1][i][j], borda[2][i][j], borda[3][i][j]);
		for(int k=0; k<4; k++) {
			if((k&1)&&seg[k][0][0]>borda[k][i][j]) ok=0;  
			if((~k&1)&&seg[k][0][0]<borda[k][i][j]) ok=0;  
		}
		if(ok) respf++;
	}

	return respf;
}

Compilation message

rect.cpp: In function 'void histogrami()':
rect.cpp:24:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, -1});
   ^~~~~
rect.cpp:24:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, -1});
                              ^~
rect.cpp:30:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, m});
   ^~~~~
rect.cpp:30:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, m});
                              ^~
rect.cpp: In function 'void histogramj()':
rect.cpp:41:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, -1});
   ^~~~~
rect.cpp:41:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, -1});
                              ^~
rect.cpp:47:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(st.size()) st.pop(); st.push({INF, n});
   ^~~~~
rect.cpp:47:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(st.size()) st.pop(); st.push({INF, n});
                              ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 5 ms 2940 KB Output is correct
4 Correct 5 ms 2812 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 5 ms 2808 KB Output is correct
20 Correct 4 ms 2808 KB Output is correct
21 Correct 3 ms 1144 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 5 ms 2940 KB Output is correct
4 Correct 5 ms 2812 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 19 ms 8184 KB Output is correct
18 Correct 19 ms 8184 KB Output is correct
19 Correct 19 ms 8188 KB Output is correct
20 Correct 14 ms 8184 KB Output is correct
21 Correct 16 ms 8056 KB Output is correct
22 Correct 16 ms 8184 KB Output is correct
23 Correct 16 ms 8184 KB Output is correct
24 Correct 14 ms 7292 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 5 ms 2808 KB Output is correct
28 Correct 4 ms 2808 KB Output is correct
29 Correct 3 ms 1144 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 5 ms 2940 KB Output is correct
4 Correct 5 ms 2812 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 19 ms 8184 KB Output is correct
18 Correct 19 ms 8184 KB Output is correct
19 Correct 19 ms 8188 KB Output is correct
20 Correct 14 ms 8184 KB Output is correct
21 Correct 16 ms 8056 KB Output is correct
22 Correct 16 ms 8184 KB Output is correct
23 Correct 16 ms 8184 KB Output is correct
24 Correct 14 ms 7292 KB Output is correct
25 Correct 128 ms 26624 KB Output is correct
26 Correct 130 ms 26484 KB Output is correct
27 Correct 131 ms 26688 KB Output is correct
28 Correct 77 ms 26488 KB Output is correct
29 Correct 112 ms 26552 KB Output is correct
30 Correct 121 ms 26712 KB Output is correct
31 Correct 132 ms 26612 KB Output is correct
32 Correct 109 ms 26352 KB Output is correct
33 Correct 2 ms 504 KB Output is correct
34 Correct 2 ms 504 KB Output is correct
35 Correct 5 ms 2808 KB Output is correct
36 Correct 4 ms 2808 KB Output is correct
37 Correct 3 ms 1144 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 5 ms 2940 KB Output is correct
4 Correct 5 ms 2812 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 19 ms 8184 KB Output is correct
18 Correct 19 ms 8184 KB Output is correct
19 Correct 19 ms 8188 KB Output is correct
20 Correct 14 ms 8184 KB Output is correct
21 Correct 16 ms 8056 KB Output is correct
22 Correct 16 ms 8184 KB Output is correct
23 Correct 16 ms 8184 KB Output is correct
24 Correct 14 ms 7292 KB Output is correct
25 Correct 128 ms 26624 KB Output is correct
26 Correct 130 ms 26484 KB Output is correct
27 Correct 131 ms 26688 KB Output is correct
28 Correct 77 ms 26488 KB Output is correct
29 Correct 112 ms 26552 KB Output is correct
30 Correct 121 ms 26712 KB Output is correct
31 Correct 132 ms 26612 KB Output is correct
32 Correct 109 ms 26352 KB Output is correct
33 Correct 990 ms 144696 KB Output is correct
34 Correct 996 ms 144676 KB Output is correct
35 Correct 985 ms 144676 KB Output is correct
36 Correct 986 ms 144732 KB Output is correct
37 Correct 2778 ms 144792 KB Output is correct
38 Correct 2758 ms 144836 KB Output is correct
39 Correct 2765 ms 145116 KB Output is correct
40 Correct 2536 ms 135796 KB Output is correct
41 Correct 1022 ms 142568 KB Output is correct
42 Correct 1132 ms 142572 KB Output is correct
43 Correct 2634 ms 143396 KB Output is correct
44 Correct 2610 ms 145244 KB Output is correct
45 Correct 1081 ms 121188 KB Output is correct
46 Correct 1087 ms 72924 KB Output is correct
47 Correct 2512 ms 144336 KB Output is correct
48 Correct 2411 ms 145272 KB Output is correct
49 Correct 2 ms 504 KB Output is correct
50 Correct 2 ms 504 KB Output is correct
51 Correct 5 ms 2808 KB Output is correct
52 Correct 4 ms 2808 KB Output is correct
53 Correct 3 ms 1144 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Runtime error 315 ms 129756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 5 ms 2940 KB Output is correct
4 Correct 5 ms 2812 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 1144 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 19 ms 8184 KB Output is correct
18 Correct 19 ms 8184 KB Output is correct
19 Correct 19 ms 8188 KB Output is correct
20 Correct 14 ms 8184 KB Output is correct
21 Correct 16 ms 8056 KB Output is correct
22 Correct 16 ms 8184 KB Output is correct
23 Correct 16 ms 8184 KB Output is correct
24 Correct 14 ms 7292 KB Output is correct
25 Correct 128 ms 26624 KB Output is correct
26 Correct 130 ms 26484 KB Output is correct
27 Correct 131 ms 26688 KB Output is correct
28 Correct 77 ms 26488 KB Output is correct
29 Correct 112 ms 26552 KB Output is correct
30 Correct 121 ms 26712 KB Output is correct
31 Correct 132 ms 26612 KB Output is correct
32 Correct 109 ms 26352 KB Output is correct
33 Correct 990 ms 144696 KB Output is correct
34 Correct 996 ms 144676 KB Output is correct
35 Correct 985 ms 144676 KB Output is correct
36 Correct 986 ms 144732 KB Output is correct
37 Correct 2778 ms 144792 KB Output is correct
38 Correct 2758 ms 144836 KB Output is correct
39 Correct 2765 ms 145116 KB Output is correct
40 Correct 2536 ms 135796 KB Output is correct
41 Correct 1022 ms 142568 KB Output is correct
42 Correct 1132 ms 142572 KB Output is correct
43 Correct 2634 ms 143396 KB Output is correct
44 Correct 2610 ms 145244 KB Output is correct
45 Correct 1081 ms 121188 KB Output is correct
46 Correct 1087 ms 72924 KB Output is correct
47 Correct 2512 ms 144336 KB Output is correct
48 Correct 2411 ms 145272 KB Output is correct
49 Incorrect 7 ms 1272 KB Output isn't correct
50 Halted 0 ms 0 KB -