글 읽기 - 혹시 제 구현이나 로직에 잘못된 점이 있나요?

upsk1 2년 전 0

x축의 좌표를 +20만해서 세그먼트트리에 저장하고 , y축을 오름차순 정렬하여 , 같은 y축의 별들을 세그에서 다 제거한 후

각 i 인덱스의 x축 기준 왼쪽위 별들과 오른쪽위 별들의 개수를 찾아 서로 곱해준후 정답에 더하고 mod를 해줬습니다

질문게시판에 있는 모든 테케와 스스로 몇가지 대입해봤지만 제 능력으로는 찾기 힘들어서 도움 요청드립니다..

#include <bits/stdc++.h>
using namespace std;
struct A {
	int x, y;
};
bool cmp(A a1, A a2) {
	if (a1.y == a2.y) {
		return a1.x < a2.x;
	}
	return a1.y < a2.y;
}
A pos[200001];
int a[400001], d[1600001];
const int num = 400000;
const long long mod = 1000000007;
void init(int node, int start, int end) {
	if (start == end) {
		d[node] = a[start];
		return;
	}
	int mid = (start + end) / 2;
	init(node * 2, start, mid);
	init(node * 2 + 1, mid + 1, end);
	d[node] = d[node * 2] + d[node * 2 + 1];
}
int query(int node, int start, int end, int i, int j) {
	if (start > j || end < i)return 0;
	if (start >= i && end <= j)return d[node];
	int mid = (start + end) / 2;
	return query(node * 2, start, mid, i, j) + query(node * 2 + 1, mid + 1, end, i, j);
}
void update(int node, int start, int end, int i) {
	if (start > i || end < i)return;
	d[node]--;
	if (start == end)return;
	int mid = (start + end) / 2;
	update(node * 2, start, mid, i);
	update(node * 2 + 1, mid + 1, end, i);
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> pos[i].x >> pos[i].y;
		pos[i].x += 200000;
		pos[i].y += 200000;
		a[pos[i].x]++;
	}
	sort(pos, pos + n, cmp);
	init(1, 0, num);
	long long ans = 0;
	int last = -1;
	for (int i = 0; i < n; i++) {
		if (i > last) {
			for (int j = i; j < n; j++) {
				if (pos[i].y == pos[j].y) {
					last = j;
					update(1, 0, num, pos[j].x);
				}
				else break;
			}
		}
		//cout << pos[i].x << ' ' << pos[i].y << '\n';
		//cout << last << ' ';
		if (pos[i].x == 0 || pos[i].x == n) {
			//cout << "통과\n";
			continue;
		}
		long long t1 = query(1, 0, num, 0,pos[i].x-1);
		long long t2 = query(1, 0, num, pos[i].x + 1, num);
		ans += t1 * t2;
		ans %= mod;
		//cout << ans << '\n';
	}
	cout << ans << '\n';
}

junseo 2년 전 1

66번째 줄이 잘못된 것 같습니다.

upsk1 2년 전 0

와.. n이아니였군요

감사합니다 !!

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

문제

문제

출처

ICPC

혹시 제 구현이나 로직에 잘못된 점이 있나요?

upsk1 2년 전 0

junseo 2년 전 1

upsk1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말