글 읽기 - 어디서 틀렸는지 모르겠습니다. (직사각형)

gs25 2년 전 0

일반적인 스위핑 + 세그먼트 트리로 풀었는데 어디서 틀렸는지 도저히 모르겠습니다. 좀 추하지만 http://web.mit.edu/acmicpc/www... 여기 들어가서 테스트 케이스 다 넣어봤는데도 다 맞게 나오는데 어디서 틀렸는지 모르겠습니다. 고수님들 봐주시면 감사할 것 같습니다 ㅠㅠ

#define _CRT_SECURE_NO_DEPRECATE
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll cnt[1600000] = {};
ll seg[1600000] = {};

vector<ll> xx;
vector<ll> yy;

void query(ll node, ll x, ll y, ll val, ll L, ll R) {       // L 과 R 이 고정 x,y가 가변
	if (L <= x && y <= R) {
		cnt[node] += val;
		if (cnt[node] != 0) seg[node] = yy[y] - yy[x - 1];
		else seg[node] = seg[node * 2] + seg[node * 2 + 1];
		return;
	}
	if (R<x || L>y) return;

	ll mid = (x + y) >> 1;
	query(node * 2, x, mid, val, L, R);
	query(node * 2 + 1, mid + 1, y, val, L, R);
	if (cnt[node]) seg[node] = yy[y] - yy[x - 1];
	else seg[node] = seg[node * 2] + seg[node * 2 + 1];
	return;
}

struct rec {
	ll x, y1, y2, key;
};

bool cmp(rec& a, rec& b) {
	return a.x < b.x;
}

int main(void) {
	//freopen("C:\\Users\\김서진\\Desktop\\team1_contest\\rectangle\\1.in", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(NULL); 
	int N;
	cin >> N;
	vector<rec> rec_set;
	for (int i = 0; i < N; i++) {
		ll x1, x2, y1, y2;
		cin >> x1 >> x2 >> y1 >> y2;
		xx.push_back(x1); xx.push_back(x2); yy.push_back(y1); yy.push_back(y2);
		rec_set.push_back({ x1,y1,y2,1 });
		rec_set.push_back({ x2,y1,y2,-1 });
	}
	sort(xx.begin(), xx.end());
	sort(yy.begin(), yy.end());
	yy.erase(unique(yy.begin(), yy.end()), yy.end());
	sort(rec_set.begin(), rec_set.end(), cmp);

	ll sum = 0;
	ll bx = 0;
	for (int i = 0; i < 2 * N; i++) {
		ll x=rec_set[i].x, y1=rec_set[i].y1, y2=rec_set[i].y2, key=rec_set[i].key;
		sum += seg[1] * (ll)(x - bx);
		ll s = lower_bound(yy.begin(), yy.end(), y1) - yy.begin(), e = lower_bound(yy.begin(), yy.end(), y2) - yy.begin();
		query(1, 1, yy.size()-1, key, s + 1, e);
		bx = x;
	}
	cout << sum;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다. (직사각형)

gs25 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말