Submission #585497

#	Time	Username	Problem	Language	Result	Execution time	Memory
585497		8e7	Rectangles (IOI19_rect)	C++17	100 / 100	1958 ms	101128 KiB

rect

#include "rect.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 2505
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct BIT{
	vector<int> ch;
	int bit[maxn];
	void modify(int ind) {
		ind++;
		ch.push_back(ind);
		for (;ind < maxn;ind += ind & (-ind)) bit[ind]++;
	}
	int query(int ind) {
		ind++;
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
	void undo() {
		for (int ind:ch) {
			for (;ind < maxn;ind += ind & (-ind)) bit[ind]--;
		}
		ch.clear();
	}
} bit;
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();	
	ll ret = 0;

	vector<vector<pii> > row(m);
	vector<vector<int> > stk(m);

	auto merge = [&] (vector<pii> &vec, vector<pii> &prv) { //merges prv to vec
		int ind = 0;	
		for (auto &[f, s]:vec) {
			while (ind < prv.size() && prv[ind].ff > f) ind++;
			if (ind < prv.size() && prv[ind].ff == f) s = prv[ind].ss;
		}
		prv = vec;
		vec.clear();
	};
	for (int i = 0;i < n;i++) {
		vector<int> cstk; //col stack
		vector<pii> col;
		for (int j = 0;j < m;j++) {
			{
				vector<pii> to;
				vector<int> &s = cstk;
				int prv = -1;
				while (s.size() && a[i][j] >= a[i][s.back()]) {
					int v = a[i][s.back()];
					to.push_back({s.back(), i});	
					prv = v;
					s.pop_back();
				}
				if (prv < a[i][j] && s.size()) {
					to.push_back({s.back(), i});
				}
				s.push_back(j);

				merge(to, row[j]);

			}

			{
				vector<pii> to;
				vector<int> &s = stk[j];
				int prv = -1;
				while (s.size() && a[i][j] >= a[s.back()][j]) {
					int v = a[s.back()][j];
					to.push_back({s.back(), j});	
					prv = v;
					s.pop_back();
				}
				if (prv < a[i][j] && s.size()) {
					to.push_back({s.back(), j});
				}
				s.push_back(i);
				merge(to, col);
			}

			if (j < m-1) {
				vector<pii> orig = col;
				sort(col.begin(), col.end(), [&] (pii p, pii q){return p.ss > q.ss;});
				int ind = 0;
				debug(i, j);
				for (auto q:col) {
					while (ind < row[j+1].size() && row[j+1][ind].ff+1 >= q.ss) {
						//debug("mod", col[ind].ff);
						if (row[j+1][ind].ff < j) bit.modify(row[j+1][ind].ss);
						ind++;
					}
					if (q.ff < i-1) {
						debug(q.ff, q.ss, bit.query(q.ff+1));
						ret += bit.query(q.ff+1);
					}
				}
				bit.undo();
				col = orig;
			}
		}
	}
	return ret;
}

Compilation message (stderr)

rect.cpp: In lambda function:
rect.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    while (ind < prv.size() && prv[ind].ff > f) ind++;
      |           ~~~~^~~~~~~~~~~~
rect.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    if (ind < prv.size() && prv[ind].ff == f) s = prv[ind].ss;
      |        ~~~~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
rect.cpp:105:5: note: in expansion of macro 'debug'
  105 |     debug(i, j);
      |     ^~~~~
rect.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |      while (ind < row[j+1].size() && row[j+1][ind].ff+1 >= q.ss) {
      |             ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
rect.cpp:113:7: note: in expansion of macro 'debug'
  113 |       debug(q.ff, q.ss, bit.query(q.ff+1));
      |       ^~~~~

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