[BOJ] 2601 도서실카펫

2601번: 도서실카펫 (acmicpc.net)

2601번: 도서실카펫

알고리즘 태그 : 레이지 세그먼트 트리, 스위핑

시간 복잡도 : \(O(NlogN+MlogM)\)

 

각 얼룩 마다 어디에 카펫을 설치할 경우 이 얼룩이 지워진다는 것을 직사각형 모양의 범위로 표현할 수 있다.

이제 이 범위들을 가지고 스위핑을 하며 구간 업뎃을 해서 각 업뎃이 끝났을 때 마다 전체 구간의 최댓값을 구해주면 된다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 2e18;
const int mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 20000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int R,n,m,rx1,ry1,rx2,ry2;
int t[4000015],la[4000015];

struct Aluk {
	int x,y1,y2,val;
};
vector <Aluk> v;

void push(int x,int l,int r) {
	if(la[x]) {
		t[x] += la[x];
		if(l^r) la[x*2] += la[x], la[x*2+1] += la[x];
		la[x] = 0;
	}
}

void update(int x,int l,int r,int rl,int rr,int val) {
	push(x,l,r);
	if(rl > r||l > rr) return;
	if(rl <= l&&r <= rr) {
		la[x] += val;
		push(x,l,r); return;
	}
	int mid = (l + r) >> 1;
	update(x*2,l,mid,rl,rr,val), update(x*2+1,mid+1,r,rl,rr,val);
	t[x] = max(t[x*2],t[x*2+1]);
}

bool cmp(Aluk x,Aluk y) {
	if(x.x == y.x) return x.val > y.val;
	return x.x < y.x;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> rx1 >> ry2 >> rx2 >> ry1;
	cin >> R >> n;
	for(int i = 1;i <= n;i++) {
		int x1,y1,x2,y2; cin >> x1 >> y2 >> x2 >> y1;
		if(x2-x1 > R||y2-y1 > R) continue;
		int lx = max(rx1,x2-R), ly = max(ry1,y2-R);
		int rx = min(rx2-R,x1), ry = min(ry2-R,y1);
		v.pb({lx,ly,ry,1});
		v.pb({rx,ly,ry,-1});
	}
	sort(all(v),cmp);
	int ans = 0;
	for(Aluk now : v) {
		update(1,0,MAXM,now.y1,now.y2,now.val);
		ans = max(ans,t[1]);
	}
	cout << ans;
}