Submission #147562

#	Time	Username	Problem	Language	Result	Execution time	Memory
147562		kuroni	Rectangles (IOI19_rect)	C++17	100 / 100	1357 ms	211720 KiB

rect

#pragma once
#include <bits/stdc++.h>
#include "rect.h"
#define fi first
#define se second
using namespace std;

const int MX = 2505;

vector<int> row[MX], col[MX];
vector<pair<int, int>> pair_row, pair_col;
int bit[MX];
int lst_row[MX][MX], cnt_row[MX][MX];
int lst_col[MX][MX], cnt_col[MX][MX];

void update(int u, int v)
{
	for (; u < MX; u += u & -u)
		bit[u] += v;
}

int query(int u)
{
	int ret = 0;
	for (; u > 0; u -= u & -u)
		ret += bit[u];
	return ret;
}

pair<int, int> process(int l, int r, int cur, int lst[MX][MX], int cnt[MX][MX])
{
	if (lst[l][r] != cur - 1)
		cnt[l][r] = 0;
	cnt[l][r]++; lst[l][r] = cur;
	return {r - l - 1, cnt[l][r]};
}

long long find_ans(vector<pair<int, int>> &row, vector<pair<int, int>> &col)
{
	long long ans = 0;
	for (pair<int, int> &v : col)
		swap(v.fi, v.se);
	sort(row.begin(), row.end(), greater<pair<int, int>>());
	sort(col.begin(), col.end(), greater<pair<int, int>>());
	int pt = 0;
	for (pair<int, int> &v : row)
	{
		for (; pt < col.size() && v.fi <= col[pt].fi; pt++)
			update(col[pt].se, 1);
		ans += query(v.se);
	}
	for (int i = 0; i < pt; i++)
		update(col[i].se, -1);
	return ans;
}

long long count_rectangles(vector<vector<int>> a)
{
	bool eq;
	int m = a.size(), n = a[0].size();
	long long ans = 0;
	for (int i = 0; i < m; i++)
		row[i] = {0};
	for (int i = 0; i < n; i++)
		col[i] = {0};
	for (int i = 0; i < m - 1; i++)
		for (int j = 0; j < n - 1; j++)
		{
			eq = false;
			pair_row.clear();
			while (!row[i].empty())
			{
				int u = row[i].back();
				if (u < j && !eq)
					pair_row.push_back(process(u, j + 1, i, lst_row, cnt_row));
				eq = (a[i][u] == a[i][j + 1]);
				if (a[i][u] <= a[i][j + 1])
					row[i].pop_back();
				else
					break;
			}
			row[i].push_back(j + 1);

			eq = false;
			pair_col.clear();
			while (!col[j].empty())
			{
				int u = col[j].back();
				if (u < i && !eq)
					pair_col.push_back(process(u, i + 1, j, lst_col, cnt_col));
				eq = (a[u][j] == a[i + 1][j]);
				if (a[u][j] <= a[i + 1][j])
					col[j].pop_back();
				else
					break;
			}
			col[j].push_back(i + 1);

			ans += find_ans(pair_row, pair_col);
		}
	return ans;
}

Compilation message (stderr)

rect.cpp:1:9: warning: #pragma once in main file
 #pragma once
         ^~~~
rect.cpp: In function 'long long int find_ans(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
rect.cpp:48:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; pt < col.size() && v.fi <= col[pt].fi; pt++)
          ~~~^~~~~~~~~~~~

• 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