oj.uz

Submission #624829

# Submission time Handle Problem Language Result Execution time Memory
624829 2022-08-08T20:12:26 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
71 / 100
 5000 ms 488620 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 15013;
const int SQ = 240;
int a[200013];
int b[200013];
bool f[200013];
int s[200013];
int h, w;
int id(int i, int j){
	return i * (w + 1) + j;
}
int id2(int i, int j){
	return j * (h + 1) + i;
}

struct Range{
	short x1, x2, y1, y2; // 1D; [x1, x2] x [y1, y2]
};

vector<Range> vrs[SQ][SQ];
int qry(int x1, int x2, int y1, int y2){
	return s[id(x2 + 1, y2 + 1)] + s[id(x1, y1)] - s[id(x2 + 1, y1)] - s[id(x1, y2 + 1)];
}


struct BIT{
	short bit[N][N] = {0};
	void clear(int n){
		n += 10;
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				bit[i][j] = 0;
			}
		}
	}
	void upd(int x, int y, int v){
		x += 2; y += 2;
		for(int i = x; i < w + 10; i += i & -i){
			for(int j = y; j < w + 10; j += j & -j){
				bit[i][j] += v;
			}
		}
	}
	void upd(int x1, int x2, int y1, int y2, int v){
		upd(x2 + 1, y2 + 1, v);
		upd(x1, y2 + 1, -v);
		upd(x2 + 1, y1, -v);
		upd(x1, y1, v);
	}
	int qry(int x, int y){
		x += 2; y += 2;
		int ret = 0;
		for(int i = x; i; i -= i & -i){
			for(int j = y; j; j -= j & -j){
				ret += bit[i][j];
			}
		}
		return ret;
	}
	int qry(int x1, int x2, int y1, int y2){
		return qry(x2, y2) - qry(x2, y1 - 1) - qry(x1 - 1, y2) + qry(x1 - 1, y1 - 1);
	}
} bit;

int g(vector<Range> vr, int h){
	bit.clear(w);
	for(auto r : vr){
		bit.upd(r.x1, r.x2, r.y1, r.y2, 1);
	}
	int ans = 0;
	for(int i = 0; i < w; i++){
		for(int j = i; j < w; j++){
			ans += bit.qry(i, j) == h * (j - i + 1) - 1;
		}
	}
	return ans;
}

int32_t main(){
	cin >> h >> w;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			cin >> a[id(i, j)];
		}
	}
	if(h > w){
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				b[id2(i, j)] = a[id(i, j)];
			}
		}
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				a[id2(i, j)] = b[id2(i, j)];
			}
		}
		swap(w, h);
	}
	{
		set<int> S; map<int, int> M;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				S.insert(a[id(i, j)]);
			}
		}
		int idx = 0;
		for(auto j : S){
			M[j] = idx++;
		}
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				a[id(i, j)] = M[a[id(i, j)]];
			}
		}
	}
	
	int ans = 0;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w - 1; j++){
			int v1 = a[id(i, j)], v2 = a[id(i, j + 1)];
			if(v1 > v2) swap(v1, v2);
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
				}
			}
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
				}
			}
			int x1 = i, x2 = i, y1 = j, y2 = j + 1;
			for(int x3 = 0; x3 <= x1; x3++){
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					int y3 = INT16_MAX, y4 = INT16_MIN;
					{
						int l = 0, r = y1;
						while(l != r){
							int mid = (l + r) / 2;
							if(qry(x3, x4, mid, y1)){
								l = mid + 1;
							}else{
								r = mid;
							}
						}
						y3 = l;
					}
					{
						int l = y2, r = w - 1;
						while(l != r){
							int mid = (l + r + 1) / 2;
							if(qry(x3, x4, y2, mid)){
								r = mid - 1;
							}else{
								l = mid;
							}
						}
						y4 = l;
					}
					vrs[x3][x4].push_back({y3, y1, y2, y4});
				}
			}
		}
	}

	for(int i = 0; i < h - 1; i++){
		for(int j = 0; j < w; j++){
			int v1 = a[id(i, j)], v2 = a[id(i + 1, j)];
			if(v1 > v2) swap(v1, v2);
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
				}
			}
			for(int x = 0; x < h; x++){
				for(int y = 0; y < w; y++){
					s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
				}
			}
			int x1 = i, x2 = i + 1, y1 = j, y2 = j;
			for(int x3 = 0; x3 <= x1; x3++){
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					int y3 = INT16_MAX, y4 = INT16_MIN;
					{
						int l = 0, r = y1;
						while(l != r){
							int mid = (l + r) / 2;
							if(qry(x3, x4, mid, y1)){
								l = mid + 1;
							}else{
								r = mid;
							}
						}
						y3 = l;
					}
					{
						int l = y2, r = w - 1;
						while(l != r){
							int mid = (l + r + 1) / 2;
							if(qry(x3, x4, y2, mid)){
								r = mid - 1;
							}else{
								l = mid;
							}
						}
						y4 = l;
					}
					vrs[x3][x4].push_back({y3, y1, y2, y4});
				}
			}
		}
	}
	for(int x1 = 0; x1 < h; x1++){
		for(int x2 = x1; x2 < h; x2++){
			ans += g(vrs[x1][x2], x2 - x1 + 1);
		}
	}
	cout << ans << endl;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:163:29: warning: narrowing conversion of 'y3' from 'int' to 'short int' [-Wnarrowing]
  163 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                             ^~
Main.cpp:163:33: warning: narrowing conversion of 'y1' from 'int' to 'short int' [-Wnarrowing]
  163 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                 ^~
Main.cpp:163:37: warning: narrowing conversion of 'y2' from 'int' to 'short int' [-Wnarrowing]
  163 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                     ^~
Main.cpp:163:41: warning: narrowing conversion of 'y4' from 'int' to 'short int' [-Wnarrowing]
  163 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                         ^~
Main.cpp:212:29: warning: narrowing conversion of 'y3' from 'int' to 'short int' [-Wnarrowing]
  212 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                             ^~
Main.cpp:212:33: warning: narrowing conversion of 'y1' from 'int' to 'short int' [-Wnarrowing]
  212 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                 ^~
Main.cpp:212:37: warning: narrowing conversion of 'y2' from 'int' to 'short int' [-Wnarrowing]
  212 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                     ^~
Main.cpp:212:41: warning: narrowing conversion of 'y4' from 'int' to 'short int' [-Wnarrowing]
  212 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                         ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Execution timed out 5081 ms 488620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 51 ms 12428 KB Output is correct
8 Correct 50 ms 12424 KB Output is correct
9 Correct 31 ms 2660 KB Output is correct
10 Correct 68 ms 7292 KB Output is correct
11 Correct 37 ms 6056 KB Output is correct
12 Correct 36 ms 6068 KB Output is correct
13 Correct 60 ms 7180 KB Output is correct
14 Correct 35 ms 4516 KB Output is correct
15 Correct 48 ms 5196 KB Output is correct
16 Correct 34 ms 3396 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 51 ms 12428 KB Output is correct
8 Correct 50 ms 12424 KB Output is correct
9 Correct 31 ms 2660 KB Output is correct
10 Correct 68 ms 7292 KB Output is correct
11 Correct 37 ms 6056 KB Output is correct
12 Correct 36 ms 6068 KB Output is correct
13 Correct 60 ms 7180 KB Output is correct
14 Correct 35 ms 4516 KB Output is correct
15 Correct 48 ms 5196 KB Output is correct
16 Correct 34 ms 3396 KB Output is correct
17 Correct 1450 ms 126884 KB Output is correct
18 Correct 575 ms 8180 KB Output is correct
19 Correct 578 ms 6088 KB Output is correct
20 Correct 2457 ms 151620 KB Output is correct
21 Correct 1505 ms 82224 KB Output is correct
22 Correct 1779 ms 104780 KB Output is correct
23 Correct 1565 ms 100172 KB Output is correct
24 Correct 1057 ms 57488 KB Output is correct
25 Correct 1475 ms 75644 KB Output is correct
26 Correct 1503 ms 83540 KB Output is correct
27 Correct 700 ms 22364 KB Output is correct
28 Correct 778 ms 25240 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 2 ms 1748 KB Output is correct
7 Correct 51 ms 12428 KB Output is correct
8 Correct 50 ms 12424 KB Output is correct
9 Correct 31 ms 2660 KB Output is correct
10 Correct 68 ms 7292 KB Output is correct
11 Correct 37 ms 6056 KB Output is correct
12 Correct 36 ms 6068 KB Output is correct
13 Correct 60 ms 7180 KB Output is correct
14 Correct 35 ms 4516 KB Output is correct
15 Correct 48 ms 5196 KB Output is correct
16 Correct 34 ms 3396 KB Output is correct
17 Correct 1450 ms 126884 KB Output is correct
18 Correct 575 ms 8180 KB Output is correct
19 Correct 578 ms 6088 KB Output is correct
20 Correct 2457 ms 151620 KB Output is correct
21 Correct 1505 ms 82224 KB Output is correct
22 Correct 1779 ms 104780 KB Output is correct
23 Correct 1565 ms 100172 KB Output is correct
24 Correct 1057 ms 57488 KB Output is correct
25 Correct 1475 ms 75644 KB Output is correct
26 Correct 1503 ms 83540 KB Output is correct
27 Correct 700 ms 22364 KB Output is correct
28 Correct 778 ms 25240 KB Output is correct
29 Execution timed out 5059 ms 376336 KB Time limit exceeded
30 Halted 0 ms 0 KB -