oj.uz

Submission #624839

# Submission time Handle Problem Language Result Execution time Memory
624839 2022-08-08T20:55:47 Z QwertyPi Sandcastle 2 (JOI22_ho_t5) C++14
71 / 100
 4046 ms 1048576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("avx2")
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 PartialSum2D{
	short a[N][N] = {0}, ps[N][N] = {0};
	void clear(int n){
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				a[i][j] = ps[i][j] = 0;
			}
		}
	}
	void upd(int x1, int x2, int y1, int y2, int v){
		a[x2 + 1][y2 + 1] += v;
		a[x1][y2 + 1] -= v;
		a[x2 + 1][y1] -= v;
		a[x1][y1] += v;
	}
	void run(int n){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + a[i - 1][j - 1];
			}
		}
	}
	int qry(int x, int y){
		return ps[x + 1][y + 1];
	}
} ps;

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

int32_t main(){
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
	
	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++){
				int y3 = 0, y4 = w - 1;
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					while(qry(x3, x4, y3, y1)) y3++;
					while(qry(x3, x4, y2, y4)) y4--;
					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++){
				int y3 = 0, y4 = w - 1;
				for(int x4 = x2; x4 < h; x4++){
					if(qry(x3, x4, y1, y2)) continue;
					while(qry(x3, x4, y3, y1)) y3++;
					while(qry(x3, x4, y2, y4)) y4--;
					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:4:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("avx2")
      |                            ^
Main.cpp:14:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   14 | int id(int i, int j){
      |                    ^
Main.cpp:17:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   17 | int id2(int i, int j){
      |                     ^
Main.cpp:26:39: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   26 | int qry(int x1, int x2, int y1, int y2){
      |                                       ^
Main.cpp:33:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   33 |  void clear(int n){
      |                  ^
Main.cpp:40:48: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   40 |  void upd(int x1, int x2, int y1, int y2, int v){
      |                                                ^
Main.cpp:46:16: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   46 |  void run(int n){
      |                ^
Main.cpp:53:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   53 |  int qry(int x, int y){
      |                      ^
Main.cpp:58:31: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   58 | int g(vector<Range>& vr, int h){
      |                               ^
Main.cpp:73:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   73 | int32_t main(){
      |              ^
Main.cpp: In function 'int32_t main()':
Main.cpp:136:29: warning: narrowing conversion of 'y3' from 'int' to 'short int' [-Wnarrowing]
  136 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                             ^~
Main.cpp:136:33: warning: narrowing conversion of 'y1' from 'int' to 'short int' [-Wnarrowing]
  136 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                 ^~
Main.cpp:136:37: warning: narrowing conversion of 'y2' from 'int' to 'short int' [-Wnarrowing]
  136 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                     ^~
Main.cpp:136:41: warning: narrowing conversion of 'y4' from 'int' to 'short int' [-Wnarrowing]
  136 |      vrs[x3][x4].push_back({y3, y1, y2, y4});
      |                                         ^~
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});
      |                                         ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Runtime error 4025 ms 1048576 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 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 2 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 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 2 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 16 ms 22740 KB Output is correct
8 Correct 17 ms 22860 KB Output is correct
9 Correct 13 ms 2828 KB Output is correct
10 Correct 17 ms 7428 KB Output is correct
11 Correct 14 ms 10256 KB Output is correct
12 Correct 13 ms 10068 KB Output is correct
13 Correct 26 ms 7380 KB Output is correct
14 Correct 13 ms 4692 KB Output is correct
15 Correct 14 ms 5392 KB Output is correct
16 Correct 13 ms 3540 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 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 2 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 16 ms 22740 KB Output is correct
8 Correct 17 ms 22860 KB Output is correct
9 Correct 13 ms 2828 KB Output is correct
10 Correct 17 ms 7428 KB Output is correct
11 Correct 14 ms 10256 KB Output is correct
12 Correct 13 ms 10068 KB Output is correct
13 Correct 26 ms 7380 KB Output is correct
14 Correct 13 ms 4692 KB Output is correct
15 Correct 14 ms 5392 KB Output is correct
16 Correct 13 ms 3540 KB Output is correct
17 Correct 203 ms 250768 KB Output is correct
18 Correct 193 ms 8644 KB Output is correct
19 Correct 176 ms 8940 KB Output is correct
20 Correct 556 ms 152272 KB Output is correct
21 Correct 350 ms 82612 KB Output is correct
22 Correct 438 ms 104652 KB Output is correct
23 Correct 386 ms 100388 KB Output is correct
24 Correct 317 ms 57468 KB Output is correct
25 Correct 327 ms 75960 KB Output is correct
26 Correct 393 ms 83672 KB Output is correct
27 Correct 238 ms 22764 KB Output is correct
28 Correct 254 ms 25572 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 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 2 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 16 ms 22740 KB Output is correct
8 Correct 17 ms 22860 KB Output is correct
9 Correct 13 ms 2828 KB Output is correct
10 Correct 17 ms 7428 KB Output is correct
11 Correct 14 ms 10256 KB Output is correct
12 Correct 13 ms 10068 KB Output is correct
13 Correct 26 ms 7380 KB Output is correct
14 Correct 13 ms 4692 KB Output is correct
15 Correct 14 ms 5392 KB Output is correct
16 Correct 13 ms 3540 KB Output is correct
17 Correct 203 ms 250768 KB Output is correct
18 Correct 193 ms 8644 KB Output is correct
19 Correct 176 ms 8940 KB Output is correct
20 Correct 556 ms 152272 KB Output is correct
21 Correct 350 ms 82612 KB Output is correct
22 Correct 438 ms 104652 KB Output is correct
23 Correct 386 ms 100388 KB Output is correct
24 Correct 317 ms 57468 KB Output is correct
25 Correct 327 ms 75960 KB Output is correct
26 Correct 393 ms 83672 KB Output is correct
27 Correct 238 ms 22764 KB Output is correct
28 Correct 254 ms 25572 KB Output is correct
29 Runtime error 4046 ms 1048576 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -