oj.uz

Submission #956918

# Submission time Handle Problem Language Result Execution time Memory
956918 2024-04-02T16:42:37 Z Macker Rectangles (IOI19_rect) C++17
10 / 100
 556 ms 372708 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define int ll
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<signed>> 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(j, m){
		vector<int> cur;
		vector<int> res;
		FOR(i, n){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(i, n){
			st[i][j].mny = res[i];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(i, n){
			st[i][j].mxy = n - res[i] - 1;
		}
	}
	
	vector<vector<pii>> ord(7000005);
	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 + 1; i < mxy; i++){
				for (int j = mnx + 1; j < mxx; j++) {
					if(!st[i][j].on) {f = 1; break;}
					if(st[i][j].mnx < mnx) {f = 1; break;}
					if(st[i][j].mny < mny) {f = 1; break;}
					if(st[i][j].mxx > mxx) {f = 1; break;}
					if(st[i][j].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 110 ms 164648 KB Output is correct
2 Correct 65 ms 164700 KB Output is correct
3 Correct 68 ms 164852 KB Output is correct
4 Correct 63 ms 164752 KB Output is correct
5 Correct 65 ms 164692 KB Output is correct
6 Correct 64 ms 164692 KB Output is correct
7 Correct 65 ms 164696 KB Output is correct
8 Correct 65 ms 164688 KB Output is correct
9 Incorrect 64 ms 164732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 164648 KB Output is correct
2 Correct 65 ms 164700 KB Output is correct
3 Correct 68 ms 164852 KB Output is correct
4 Correct 63 ms 164752 KB Output is correct
5 Correct 65 ms 164692 KB Output is correct
6 Correct 64 ms 164692 KB Output is correct
7 Correct 65 ms 164696 KB Output is correct
8 Correct 65 ms 164688 KB Output is correct
9 Incorrect 64 ms 164732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 164648 KB Output is correct
2 Correct 65 ms 164700 KB Output is correct
3 Correct 68 ms 164852 KB Output is correct
4 Correct 63 ms 164752 KB Output is correct
5 Correct 65 ms 164692 KB Output is correct
6 Correct 64 ms 164692 KB Output is correct
7 Correct 65 ms 164696 KB Output is correct
8 Correct 65 ms 164688 KB Output is correct
9 Incorrect 64 ms 164732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 164648 KB Output is correct
2 Correct 65 ms 164700 KB Output is correct
3 Correct 68 ms 164852 KB Output is correct
4 Correct 63 ms 164752 KB Output is correct
5 Correct 65 ms 164692 KB Output is correct
6 Correct 64 ms 164692 KB Output is correct
7 Correct 65 ms 164696 KB Output is correct
8 Correct 65 ms 164688 KB Output is correct
9 Incorrect 64 ms 164732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 165292 KB Output is correct
2 Correct 71 ms 165200 KB Output is correct
3 Correct 79 ms 165400 KB Output is correct
4 Correct 64 ms 164908 KB Output is correct
5 Correct 78 ms 165204 KB Output is correct
6 Correct 71 ms 165204 KB Output is correct
7 Correct 72 ms 165200 KB Output is correct
8 Correct 66 ms 165176 KB Output is correct
9 Correct 73 ms 165204 KB Output is correct
10 Correct 70 ms 164948 KB Output is correct
11 Correct 72 ms 165200 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 164772 KB Output is correct
2 Incorrect 556 ms 372708 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 164648 KB Output is correct
2 Correct 65 ms 164700 KB Output is correct
3 Correct 68 ms 164852 KB Output is correct
4 Correct 63 ms 164752 KB Output is correct
5 Correct 65 ms 164692 KB Output is correct
6 Correct 64 ms 164692 KB Output is correct
7 Correct 65 ms 164696 KB Output is correct
8 Correct 65 ms 164688 KB Output is correct
9 Incorrect 64 ms 164732 KB Output isn't correct
10 Halted 0 ms 0 KB -