Submission #621279

#	Time	Username	Problem	Language	Result	Execution time	Memory
621279		cheissmart	Rectangles (IOI19_rect)	C++14	100 / 100	4117 ms	781848 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
#ifdef CHEISSMART
void dbg() { cerr << "]" << endl; }
template<class H, class ...T> void dbg(H h, T... t) {
	cerr << to_string(h);
	if(sizeof...(t)) cerr << ", ";
	dbg(t...);
}
 
#define debug(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ <<"]: [", dbg(__VA_ARGS__);
#else
#define debug(...)
#endif
 
const int INF = 1e9 + 7, N = 3000;
 
int bit[N];
 
void add(int pos, int val) {
	for(; pos < N; pos += pos & -pos)
		bit[pos] += val;
}
int qry(int pos) {
	int res = 0;
	for(; pos; pos -= pos & -pos)
		res += bit[pos];
	return res;
}
 
ll count_rectangles(V<vi> a) {
	int n = SZ(a), m = SZ(a[0]);
	V<V<V<pair<short, short>>>> ver(n, V<V<pair<short, short>>>(m));
	V<V<V<pair<short, short>>>> hor(n, V<V<pair<short, short>>>(m));
	auto add_hor = [&] (int i, int j, int jj) {
		if(jj == j + 1) return;
		hor[i][j].EB(jj, i);
	};
	auto add_ver = [&] (int i, int j, int ii) {
		if(ii == i + 1) return;
		ver[i][j].EB(ii, j);
	};

	for(int i = 0; i < n; i++) {
		vi stk;
		for(int j = m - 1; j >= 0; j--) {
			while(SZ(stk) && a[i][stk.back()] < a[i][j]) {
				add_hor(i, j, stk.back());
				stk.pop_back();
			}
			if(SZ(stk))
				add_hor(i, j, stk.back());
			if(SZ(stk) && a[i][stk.back()] == a[i][j])
				stk.pop_back();
			stk.PB(j);
		}
	}
	for(int j = 0; j < m; j++) {
		vi stk;
		for(int i = n - 1; i >= 0; i--) {
			while(SZ(stk) && a[stk.back()][j] < a[i][j]) {
				add_ver(i, j, stk.back());
				stk.pop_back();
			}
			if(SZ(stk))
				add_ver(i, j, stk.back());
			if(SZ(stk) && a[stk.back()][j] == a[i][j])
				stk.pop_back();
			stk.PB(i);
		}
	}
	for(int i = n - 2; i >= 0; i--) {
		for(int j = 0; j < m; j++) {
			map<short, short> mp;
			for(auto[he, be]:hor[i + 1][j])
				mp[he] = be;

			V<pair<short, short>> todo;
			for(auto[jj, ii]:hor[i][j]) {
				if(mp.count(jj))
					todo.EB(jj, mp[jj]);
				else
					todo.EB(jj, ii);
			}
			hor[i][j] = todo;
		}
	}
	for(int j = m - 2; j >= 0; j--) {
		for(int i = 0; i < n; i++) {
			map<short, short> mp;
			for(auto[he, be]:ver[i][j + 1])
				mp[he] = be;

			V<pair<short, short>> todo;
			for(auto[ii, jj]:ver[i][j])
				if(mp.count(ii))
					todo.EB(ii, mp[ii]);
				else
					todo.EB(ii, jj);
			ver[i][j] = todo;
		}
	}
	ll ans = 0;
	for(int i = 1; i < n - 1; i++) {
		for(int j = 1; j < m - 1; j++) {
			V<pi> aux;
			for(auto[d, right]:ver[i - 1][j])
				aux.EB(right, d);
			V<pi> tt;
			for(auto[r, down]:hor[i][j - 1])
				tt.EB(r, down);
			if(aux.empty() || tt.empty()) continue;
 
			sort(ALL(aux));
			sort(ALL(tt), greater<pi>());

			vi undo;
			for(auto[r, down]:tt) {
				while(SZ(aux) && aux.back().F >= r - 1) {
					int d = aux.back().S;
					add(d, 1);
					undo.PB(d);
					aux.pop_back();
				}
				ans += qry(down + 1);
			}
			for(int d:undo)
				add(d, -1);
		}
	}
	return ans;
 
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:91:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |    for(auto[he, be]:hor[i + 1][j])
      |            ^
rect.cpp:95:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |    for(auto[jj, ii]:hor[i][j]) {
      |            ^
rect.cpp:107:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |    for(auto[he, be]:ver[i][j + 1])
      |            ^
rect.cpp:111:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |    for(auto[ii, jj]:ver[i][j])
      |            ^
rect.cpp:123:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |    for(auto[d, right]:ver[i - 1][j])
      |            ^
rect.cpp:126:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |    for(auto[r, down]:hor[i][j - 1])
      |            ^
rect.cpp:134:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |    for(auto[r, down]:tt) {
      |            ^

• 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