앳코더90 - 028 - Cluttered Paper（★4）

https://atcoder.jp/contests/typical90/tasks/typical90_ab

028 - Cluttered Paper（★4）

 

N개의 색종이가 주어진다. 색종이의 왼쪽 위 그리고 오른쪽 아래의 좌표가 a, b, c, d로 주어진다. 색종이를 N개 두었을 때, k=1~N까지 종이가 정확히 k 겹쳐진 부분의 면적을 출력하라.

 

문제를 보면 2차원 누적합 관련 문제임을 유추할 수 있다. 

https://www.acmicpc.net/problem/11660

비슷한 문제로는 이런 문제가 있다. 하지만, 해당 방법으로는 조금 문제가 있다. 위 문제에서는 처음에 배열이 주어져 있는 상태에서 누적합을 구하지만 우리가 풀 문제에서는 색종이를 일일이 더하며 그래프를 만들어야한다. 최악의 case에서는 1000*1000 색종이를 N (10^5) 만큼 더해서 포갰을 때, 시간 초과가 날 것이다. 이 누적합 그래프를 만드는 효율적인 방법이 있을까? 라고 한다면 존재한다.

 

imos법이다.

https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0 

누적합의 확장, imos법

해당 블로그에서 설명을 아주 잘해놔서 참고하면 된다.

 

그리고 그대로 구현을 하고 전체 범위를 full scan하면 답을 구할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
//#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
//using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N;
int arr[1005][1005];
int ans[100005];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	rep(i, N)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		arr[a][b] += 1;
		arr[a][d] -= 1;
		arr[c][b] -= 1;
		arr[c][d] += 1;
	}

	rep(i, 1001)
	{
		rep1(j, 1001)
		{
			arr[i][j] += arr[i][j - 1];
		}
	}

	rep1(i, 1001)
	{
		rep(j, 1001)
		{
			arr[i][j] += arr[i-1][j];
		}
	}

	rep(i, 1001)
	{
		rep(j, 1001)
		{
			ans[arr[i][j]] += 1;
		}
	}

	rep1(i, N)
	{
		cout << ans[i] << "\n";
	}

	return 0;
}