oj.uz

Submission #956685

# Submission time Handle Problem Language Result Execution time Memory
956685 2024-04-02T10:25:08 Z Macker Rectangles (IOI19_rect) C++17
0 / 100
 2 ms 1112 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

struct node{
	int on = 0, mxx, mnx, mxy, mny;
};
vector<vector<node>> st;

vector<int> get_last_big(vector<int> v){
	int n = v.size();
	vector<int> res(n, -1);
	stack<pii> s;
	s.push({INT_MAX, -1});
	FOR(i, n){
		int a = v[i];
		while(a >= s.top().ff) s.pop();
		res[i] = s.top().ss;
		s.push({a, i});
	}
	return res;
}

long long count_rectangles(vector<vector<int>> v) {
	int n = v.size();
	int m = v[0].size();
	st.assign(n, vector<node>(m));

	FOR(i, n){
		vector<int> cur;
		vector<int> res;
		FOR(j, m){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(j, m){
			st[i][j].mnx = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, m){
			st[i][j].mxx = m - res[j] - 1;
		}
	}
	FOR(i, m){
		vector<int> cur;
		vector<int> res;
		FOR(j, n){
			cur.push_back(v[j][i]);
		}
		res = get_last_big(cur);
		FOR(j, n){
			st[j][i].mny = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, n){
			st[j][i].mxy = n - res[j] - 1;
		}
	}
	
	vector<vector<pii>> ord(21);
	FOR(i, n) FOR(j, m){
		ord[v[i][j]].push_back({i, j});
	}
	ll res = 0;
	for (auto o : ord) {
		for (auto [x, y] : o) {
			st[x][y].on = true;
		}
		for (auto [x, y] : o) {
			int mxx, mnx, mxy, mny;
			mxx = st[x][y].mxx;
			mnx = st[x][y].mnx;
			mxy = st[x][y].mxy;
			mny = st[x][y].mny;
			if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue;

			bool f = 0;
			for (int i = mny; i <= mxy; i++){
				for (int j = mnx; j <= mxx; j++) {
					if(!st[x][y].on) {f = 1; break;}
					if(st[x][y].mnx < mnx) {f = 1; break;}
					if(st[x][y].mny < mny) {f = 1; break;}
					if(st[x][y].mxx > mxx) {f = 1; break;}
					if(st[x][y].mxy > mxy) {f = 1; break;}
				}
				if(f) break;
			}
			if(!f) res++;
		}
	}
	return res;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

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