Submission #222928

#	Time	Username	Problem	Language	Result	Execution time	Memory
222928		abeker	Rectangles (IOI19_rect)	C++17	0 / 100	335 ms	441336 KiB

rect

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

class Fenwick {
	vector <int> f;
	public:
		Fenwick(int n) {
			f.resize(n + 1);
		}
		void update(int x, int val) {
			for (x++; x < f.size(); x += x & -x)
				f[x] += val;
		}
		int get(int x) {
			int res = 0;
			for (x++; x; x -= x & -x)
				res += f[x];
			return res;
		}
		int query(int l, int r) {
			return get(r) - get(l - 1);
		}
};

vector <pii> find_pairs(const vector <int> &arr) {
	int n = arr.size();
	vector <pii> res;
	stack <int> lft, rig;
	for (int i = 0; i < n; i++) {
		while (!lft.empty() && arr[lft.top()] < arr[i])
			lft.pop();
		if (!lft.empty() && lft.top() < i - 1)
			res.push_back({lft.top(), i});
		lft.push(i);
	}
	for (int i = n - 1; i >= 0; i--) {
		while (!rig.empty() && arr[rig.top()] <= arr[i])
			rig.pop();
		if (!rig.empty() && rig.top() > i + 1)
			res.push_back({i, rig.top()});
		rig.push(i); 
	}
	sort(res.begin(), res.end());
	res.resize(unique(res.begin(), res.end()) - res.begin());
	return res;
}

vector <pii> get_blocks(const vector <int> &v, int bound) {
	vector <pii> res;
	int sz = v.size(), lst = 0;
	for (int i = 0; i < sz; i++) 
		if (i == sz - 1 || v[i + 1] > v[i] + 1) {
			res.push_back({max(v[lst] - 1, 0), min(v[i] + 1, bound - 1)});
			lst = i + 1;
		}
	return res;
}

ll count_rectangles(vector <vector <int>> a) {
	int N = a.size();
	int M = a[0].size();
	
	vector <vector <vector <int>>> rows(M);
	for (int j = 0; j < M; j++)
		rows[j].resize(M);
	for (int i = 0; i < N; i++) {
		vector <pii> tmp = find_pairs(a[i]);
		for (auto it : tmp)
			rows[it.first][it.second].push_back(i);
	}
	
	vector <vector <vector <int>>> cols(N);
	for (int i = 0; i < N; i++)
		cols[i].resize(N);
	for (int j = 0; j < M; j++) {
		vector <int> curr;
		for (int i = 0; i < N; i++)
			curr.push_back(a[i][j]);
		vector <pii> tmp = find_pairs(curr);
		for (auto it : tmp)
			cols[it.first][it.second].push_back(j);
	}
	
	vector <vector <int>> in(M * M), out(M * M);
	for (int i = 0; i < N; i++)
		for (int j = i + 2; j < N; j++) {
			vector <pii> tmp = get_blocks(cols[i][j], M);
			for (auto it : tmp) 
				for (int k = it.first; k <= it.second; k++) {
					in[k * M + it.first].push_back(i * N + j);
					out[k * M + it.second].push_back(i * N + j);
				}
		}
	
	ll sol = 0;
	Fenwick loga(N * N);
	for (int i = 0; i < M; i++)
		for (int j = 0; j < M; j++) {
			for (auto it : in[i * M + j])
				loga.update(it, 1);
			vector <pii> tmp = get_blocks(rows[i][j], N);
			for (auto it : tmp)
				for (int k = it.first; k <= it.second; k++)
					sol += loga.query(k * N + it.first, k * N + it.second);
			for (auto it : out[i * M + j])
				loga.update(it, -1);
		}
	
	return sol;
}

Compilation message (stderr)

rect.cpp: In member function 'void Fenwick::update(int, int)':
rect.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (x++; x < f.size(); x += x & -x)
              ~~^~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28