oj.uz

Submission #935671

# Submission time Handle Problem Language Result Execution time Memory
935671 2024-02-29T11:03:10 Z jcelin Sandcastle 2 (JOI22_ho_t5) C++14
71 / 100
 5000 ms 91236 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

vector<vll> pf[17], vl[17];
vector<vi> mat;
int h, w;
vi vals;

bool ins(int r, int s){
	if(r < 1 or r > h or s < 1 or s > w) return 0;
	return 1;
}

ll calc(int id, int r1, int s1, int r2, int s2){
	if(r1 > r2 or s1 > s2) return 0;
	ll ret = pf[id][r2][s2] + pf[id][r1 - 1][s1 - 1] - pf[id][r1 - 1][s2] - pf[id][r2][s1 - 1];
	return ret;
}

bool check(int up, int down, int l, int r){
	if(up == down and l == r) return 1;
	ll val = 0;
	
	if(down == up){
		val = calc(12, up, l + 1, up, r - 1) + vl[8][up][l] + vl[4][down][r];
	}else if(r == l){
		val = calc(3, up + 1, l, down - 1, l) + vl[1][up][l] + vl[2][down][r];
	}else{
		val = vl[9][up][l] + vl[5][up][r] + vl[10][down][l] + vl[6][down][r];
		val += calc(15, up + 1, l + 1, down - 1, r - 1);
		val += calc(14, down, l + 1, down, r - 1);
		val += calc(13, up, l + 1, up, r - 1);
		val += calc(11, up + 1, l, down - 1, l);
		val += calc(7, up + 1, r, down - 1, r);
	}
	return (val == (ll)h * (ll)w + 1);
}

void solve(){
	cin >> h >> w;
	mat.resize(h + 1, vi(w + 1, 0));
	for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) cin >> mat[i][j], vals.PB(mat[i][j]);
	sort(all(vals));
	for(auto &x : mat) for(auto &y : x) if(y) y = lower_bound(all(vals), y) - vals.begin() + 1;

	vi vec;
	for(int m=0; m<16; m++){
		pf[m].resize(h + 1, vll(w + 1, 0));
		vl[m].resize(h + 1, vll(w + 1, 0));
		for(int i=1; i<=h; i++){
			for(int j=1; j<=w; j++){
				vec.clear();
				vec.PB(0);
				for(int k=0; k<4; k++){
					if(!(m & (1 << k))) continue;
					int ni = i + dx[k], nj = j + dy[k];
					if(!ins(ni, nj)) continue;
					vec.PB({mat[ni][nj]});
				}
				
				int val = mat[i][j];
				sort(all(vec));
				if(vec.back() < mat[i][j]) val += (h * w + 1 - mat[i][j]);
				
				auto it = lower_bound(all(vec), mat[i][j]);
				it--;
				val -= *it;
				
				vl[m][i][j] = val;
				pf[m][i][j] += pf[m][i - 1][j] + pf[m][i][j - 1] - pf[m][i - 1][j - 1] + vl[m][i][j];
			}
		}
	}
	
	
	
	int ans = 0;
	for(int up=1; up<=h; up++){
		for(int down=up; down<=h; down++){
			for(int L=1; L<=w; L++){
				for(int R=L; R<=w; R++) if(check(up, down, L, R)) ans++;
			}
		}
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 3164 KB Output is correct
8 Correct 11 ms 3164 KB Output is correct
9 Correct 10 ms 860 KB Output is correct
10 Correct 13 ms 940 KB Output is correct
11 Correct 9 ms 860 KB Output is correct
12 Correct 10 ms 1628 KB Output is correct
13 Correct 10 ms 860 KB Output is correct
14 Correct 5 ms 600 KB Output is correct
15 Correct 13 ms 860 KB Output is correct
16 Correct 11 ms 860 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 3164 KB Output is correct
8 Correct 11 ms 3164 KB Output is correct
9 Correct 10 ms 860 KB Output is correct
10 Correct 13 ms 940 KB Output is correct
11 Correct 9 ms 860 KB Output is correct
12 Correct 10 ms 1628 KB Output is correct
13 Correct 10 ms 860 KB Output is correct
14 Correct 5 ms 600 KB Output is correct
15 Correct 13 ms 860 KB Output is correct
16 Correct 11 ms 860 KB Output is correct
17 Correct 205 ms 13324 KB Output is correct
18 Correct 211 ms 2532 KB Output is correct
19 Correct 193 ms 2640 KB Output is correct
20 Correct 202 ms 2416 KB Output is correct
21 Correct 217 ms 2428 KB Output is correct
22 Correct 194 ms 2396 KB Output is correct
23 Correct 185 ms 2352 KB Output is correct
24 Correct 157 ms 2228 KB Output is correct
25 Correct 196 ms 2436 KB Output is correct
26 Correct 195 ms 2396 KB Output is correct
27 Correct 217 ms 2436 KB Output is correct
28 Correct 196 ms 2396 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 3164 KB Output is correct
8 Correct 11 ms 3164 KB Output is correct
9 Correct 10 ms 860 KB Output is correct
10 Correct 13 ms 940 KB Output is correct
11 Correct 9 ms 860 KB Output is correct
12 Correct 10 ms 1628 KB Output is correct
13 Correct 10 ms 860 KB Output is correct
14 Correct 5 ms 600 KB Output is correct
15 Correct 13 ms 860 KB Output is correct
16 Correct 11 ms 860 KB Output is correct
17 Correct 205 ms 13324 KB Output is correct
18 Correct 211 ms 2532 KB Output is correct
19 Correct 193 ms 2640 KB Output is correct
20 Correct 202 ms 2416 KB Output is correct
21 Correct 217 ms 2428 KB Output is correct
22 Correct 194 ms 2396 KB Output is correct
23 Correct 185 ms 2352 KB Output is correct
24 Correct 157 ms 2228 KB Output is correct
25 Correct 196 ms 2436 KB Output is correct
26 Correct 195 ms 2396 KB Output is correct
27 Correct 217 ms 2436 KB Output is correct
28 Correct 196 ms 2396 KB Output is correct
29 Execution timed out 5015 ms 91236 KB Time limit exceeded
30 Halted 0 ms 0 KB -