Submission #430439

#	Time	Username	Problem	Language	Result	Execution time	Memory
430439		egekabas	Rectangles (IOI19_rect)	C++14	23 / 100	1657 ms	420872 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int bit[2509];
int n, m;
void upd(int idx, int val){
	for(++idx; idx <= max(n, m)+3; idx += idx&(-idx))
		bit[idx] += val;
}
int get(int idx){
	int ret = 0;
	for(++idx; idx > 0; idx -= idx&(-idx))
		ret += bit[idx];
	return ret;
}
	
long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size(), m = a[0].size();
	
	vector<vector<vector<int>>> pos(m, vector<vector<int>>(m));
	for(int i = 0; i < n; ++i){
		vector<int> cur;
		for(int j = m-1; j >= 0; --j){
			while(cur.size() && a[i][cur.back()] < a[i][j]){
				pos[j][cur.back()].pb(i);
				cur.pop_back();
			}
			if(cur.size())
				pos[j][cur.back()].pb(i);
			while(cur.size() && a[i][cur.back()] <= a[i][j])
				cur.pop_back();
			
			cur.pb(j);
		}
	}
	vector<vector<pair<pii, int>>> maxval(m);
	
	for(int x = 0; x < m; ++x)
		for(int y = x+2; y < m; ++y)
			for(int i = 0; i < pos[x][y].size();){
				int j;
				for(j = i+1; j < pos[x][y].size(); ++j)
					if(pos[x][y][j] != pos[x][y][j-1]+1)
						break;
				int l = pos[x][y][i];
				int r = pos[x][y][j-1];
				//cout << x << ' ' << y << ' ' << l << ' ' << r << '\n';
				maxval[x].pb({{l, r}, y});
				i = j;
			}
		
	pos = vector<vector<vector<int>>>(n, vector<vector<int>>(n));
	
	for(int i = 0; i < m; ++i){
		vector<int> cur;
		for(int j = n-1; j >= 0; --j){
			while(cur.size() && a[cur.back()][i] < a[j][i]){
				pos[j][cur.back()].pb(i);
				cur.pop_back();
			}
			if(cur.size())
				pos[j][cur.back()].pb(i);
			while(cur.size() && a[cur.back()][i] <= a[j][i])
				cur.pop_back();
			
			cur.pb(j);
		}
	}
	vector<vector<pair<pii, int>>> fin(m);
	
	for(int x = 0; x < n; ++x)
		for(int y = x+2; y < n; ++y)
			for(int i = 0; i < pos[x][y].size();){
				int j;
				for(j = i+1; j < pos[x][y].size(); ++j)
					if(pos[x][y][j] != pos[x][y][j-1]+1)
						break;
				int l = pos[x][y][i];
				int r = pos[x][y][j-1];
				for(int k = l; k <= r; ++k)
					fin[k].pb({{x, y}, r});
	
				i = j;
			}
	ll ans = 0;
	for(int i = 1; i < m; ++i){
		sort(all(fin[i]));
		sort(all(maxval[i-1]));
		multiset<pii> er;
		int curidx = 0;
		for(int j = 1; j < fin[i].size(); ++j)
			assert(fin[i][j].ff.ff >= fin[i][j-1].ff.ss);
		for(auto u : fin[i]){
			while(curidx < (int)maxval[i-1].size() && maxval[i-1][curidx].ff.ff <= u.ff.ff+1){
				upd(maxval[i-1][curidx].ss, 1);
				er.insert({maxval[i-1][curidx].ff.ss, maxval[i-1][curidx].ss});
				++curidx;
			}
			while(er.size() && er.begin()->ff < u.ff.ss-1){
				upd(er.begin()->ss, -1);
				er.erase(er.begin());
			}
			int val = get(u.ss+1);
			//cout << i << ' ' << u.ss << ' ' << u.ff.ff << ' ' << u.ff.ss << ' ' << val << '\n';
			ans += val;
		}
		for(auto u : er)
			upd(u.ss, -1);
		assert(get(m) == 0);
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(int i = 0; i < pos[x][y].size();){
      |                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(j = i+1; j < pos[x][y].size(); ++j)
      |                  ~~^~~~~~~~~~~~~~~~~~
rect.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int i = 0; i < pos[x][y].size();){
      |                   ~~^~~~~~~~~~~~~~~~~~
rect.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(j = i+1; j < pos[x][y].size(); ++j)
      |                  ~~^~~~~~~~~~~~~~~~~~
rect.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int j = 1; j < fin[i].size(); ++j)
      |                  ~~^~~~~~~~~~~~~~~

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