Submission #297523

#	Time	Username	Problem	Language	Result	Execution time	Memory
297523		Saboon	Rectangles (IOI19_rect)	C++17	10 / 100	857 ms	373500 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2500 + 10;
vector<pair<int,int>> row[maxn][maxn], col[maxn][maxn];
int pre[maxn];
int dp[maxn][maxn], fen[maxn];

void add(int idx, int val){
	for (; idx < maxn; idx += idx & -idx)
		fen[idx] += val;
}

int get(int idx){
	int ret = 0;
	for (; idx; idx -= idx & -idx)
		ret += fen[idx];
	return ret;
}

long long count_rectangles(vector<vector<int>> a){
	int n = a.size(), m = a[0].size();
	for (int i = 1; i < n-1; i++){
		for (int j = 0; j < m; j++){
			pre[j] = j-1;
			while (pre[j] != -1 and a[i][j] > a[i][pre[j]])
				pre[j] = pre[pre[j]];
			if (pre[j] == -1 or a[i][pre[j]] == a[i][j] or pre[j] == j-1)
				continue;
			row[i][pre[j]+1].push_back({j-1,1});
		}
		for (int j = m-1; j >= 0; j--){
			pre[j] = j+1;
			while (pre[j] != m and a[i][j] > a[i][pre[j]])
				pre[j] = pre[pre[j]];
			if (pre[j] == j+1 or pre[j] == m)
				continue;
			row[i][j+1].push_back({pre[j]-1,1});
		}
	}
	for (int i = n-2; i >= 0; i--){
		for (int j = 0; j < m; j++)
			for (auto [x,cnt] : row[i][j])
				dp[j][x] = -1 * (dp[j][x]+1);
		for (int j = 0; j < m; j++)
			for (auto [x,cnt] : row[i+1][j])
				if (dp[j][x] > 0)
					dp[j][x] = 0;
		for (int j = 0; j < m; j++)
			for (auto &[x,cnt] : row[i][j])
				dp[j][x] *= -1, cnt = dp[j][x], x = x-j+1;
	}
	for (int j = 1; j < m-1; j++){
		for (int i = 0; i < n; i++){
			pre[i] = i-1;
			while (pre[i] != -1 and a[i][j] > a[pre[i]][j])
				pre[i] = pre[pre[i]];
			if (pre[i] == -1 or a[i][j] == a[pre[i]][j] or pre[i] == i-1)
				continue;
			col[pre[i]+1][j].push_back({i-1,1});
		}
		for (int i = n-1; i >= 0; i--){
			pre[i] = i+1;
			while (pre[i] != n and a[i][j] > a[pre[i]][j])
				pre[i] = pre[pre[i]];
			if (pre[i] == i+1 or pre[i] == n)
				continue;
			col[i+1][j].push_back({pre[i]-1,1});
		}
	}
	for (int j = m-2; j >= 1; j--){
		for (int i = 0; i < n; i++)
			for (auto [x,cnt] : col[i][j])
				dp[i][x] = -1 * (dp[i][x]+1);
		for (int i = 0; i < n; i++)
			for (auto [x,cnt] : col[i][j+1])
				if (dp[i][x] > 0)
					dp[i][x] = 0;
		for (int i = 0; i < n; i++)
			for (auto &[x,cnt] : col[i][j])
				dp[i][x] *= -1, cnt = dp[i][x], x = x-i+1;
	}
	ll ret = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			for (auto &[x,y] : row[i][j])
				swap(x,y);
			sort(row[i][j].begin(),row[i][j].end());
			sort(col[i][j].begin(),col[i][j].end());
			int ptr = 0, cnt = 0;
			for (auto [x,c1] : row[i][j]){
				while (ptr < col[i][j].size()){
					auto [y,c2] = col[i][j][ptr];
					if (y > x)
						break;
					ptr ++;
					add(c2,+1);
					cnt ++;
				}
				ret += cnt - get(c1-1);
			}
			for (int p = 0; p < ptr; p++){
				auto [y,c2] = col[i][j][p];
				add(c2,-1);
			}
		}
	}
	return ret;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while (ptr < col[i][j].size()){
      |            ~~~~^~~~~~~~~~~~~~~~~~

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