글 읽기 - 5419 왜 틀렸는지 모르겠습니다.

beawall 2년 전 0

스위핑 기법이랑 세그먼트 트리 개념을 숙지하고 구글링해서 찾은 코드에서 배운 흐름대로 비슷하게 짰는데 자꾸 50%에서 틀립니다.

islands와 segment_tree를 vector로 표현했을 때는 outofbound로 런타임 에러가 나는 것으로 보아 인덱스 참조가 어디선가 문제가 생긴것 같은데 반례도 찾을수가 없고 아무리 고쳐도 답이 없습니다,,,

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <memory.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef long long ll;
typedef pair<int, int> pii;
pii islands[75000];
int segment_tree[150010];
int n;

//segment tree의 부분합 구하기
int calc_sum(int start, int end, int node, int left, int right)
{
    if (right < start || end < left)
        return 0;
    else if (left <= start && end <= right)
        return segment_tree[node];
    int mid = (start + end) / 2;
    return calc_sum(start, mid, node * 2, left, right) + calc_sum(mid + 1, end, node * 2 + 1, left, right);
}
//segment tree 최신화하기,이 프로그램에선 diff가 항상 1
void update(int start, int end, int node, int index, int diff)
{
    if (index < start || end < index)
        return;
    segment_tree[node] += diff;
    if (start == end)
        return;
    int mid = (start + end) / 2;
    update(start, mid, node * 2, index, diff);
    update(mid + 1, end, node * 2 + 1, index, diff);
}
void solve()
{
    cin >> n;
    int x, y;
    forn(i, n)
    {
        cin >> x >> y;
        islands[i] = make_pair(x, y);
    }
    //y좌표 기준으로 오름차순 정렬, y좌표 단순화
    sort(islands, islands + n, [](pii &a, pii &b)
         { return a.second < b.second; });
    int yidx = 0;
    int prev = islands[0].second;
    islands[0].second = 0;
    for (int i = 1; i < n; i++)
    {
        if (islands[i].second != prev)
        {
            prev = islands[i].second;
            islands[i].second = ++yidx;
        }
        else
        {
            prev = islands[i].second;
            islands[i].second = yidx;
        }
    }
    memset(segment_tree, 0, sizeof(segment_tree));
    //x좌표 기준으로, x좌표가 같으면 y 기준 내림차순 정렬
    sort(islands, islands + n, [](pii &a, pii &b)
         {
             if (a.first == b.first)
                 return a.second > b.second;
             return a.first < b.first;
         });
    ll result = 0;
    for (int i = 0; i < n; i++)
    {
        result += calc_sum(0, yidx, 1, islands[i].second, yidx);
        update(0, yidx, 1, islands[i].second, 1);
    }
    cout << result << '\n';
}

bool multi = true;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    if (multi)
        cin >> t;
    while (t--)
        solve();
    return 0;
}

beawall 2년 전 0

자답합니다. segment tree의 크기를 75000의 2배에서 4배로 늘렸더니 바로 통과했습니다.

세그먼트 트리의 사이즈가 최악의 경우 150000을 초과한다는 걸 간과했네요

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

문제

문제

출처

ICPC

5419 왜 틀렸는지 모르겠습니다.

beawall 2년 전 0

beawall 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말