글 읽기 - 1퍼 입구컷 도와주세요

jshyun912 1년 전 0

구간트리 두개 짜서

하나는 거리 세는 용도 (tree) 다른 하나는 갯수 새는 용도 (tree2)로 뒀습니다

(X보다 왼쪽에 있는 거리들의 갯수 * X) - X보다 왼쪽에 있는 거리들 합 + X보다 오른쪽에 있는 거리들 합 - (X보다 오른쪽에 있는 거리들의 갯수 * X) 을 구했습니다.

예제는 다 되는거 같은데 어디서 문제일까요

import sys
input = sys.stdin.readline

MAX = 200000
MOD = 1000000007
ans = 1

tree = [ 0 for _ in range(MAX * 2) ]
tree2 = [ 0 for _ in range(MAX * 2) ]

def update():
    global tree
    global tree2

    a = X + MAX - 1
    tree[a] += X
    tree2[a] += 1

    while a >= 1:
        a //= 2
        tree[a] = tree[a * 2] + tree[a * 2 + 1]
        tree2[a] = tree2[a * 2] + tree2[a * 2 + 1]

def count1(a, b):
    a += (MAX - 1)
    b += (MAX - 1)
    dap = 0

    while a <= b:
        if a % 2 == 1:
            dap += tree[a]
            a += 1

        if b % 2 == 0:
            dap += tree[b]
            b -= 1

        a //= 2
        b //= 2

    return dap

def count2(a, b):
    a += (MAX - 1)
    b += (MAX - 1)
    dap = 0

    while a <= b:
        if a % 2 == 1:
            dap += tree2[a]
            a += 1

        if b % 2 == 0:
            dap += tree2[b]
            b -= 1

        a //= 2
        b //= 2

    return dap

N = int(input()) - 1
X = int(input())
update()

for _ in range(N):
    X = int(input())
    left = count2(1, X - 1) * X
    right = count2(X + 1, MAX) * X
    SUM = left - count1(1, X - 1) + count1(X + 1, MAX) - right
    ans *= SUM
    ans %= MOD
    update()

print(ans)

jhuni 1년 전 1

좌표가 0인 나무가 입력으로 들어왔을때 문제가 생깁니다~

jshyun912 1년 전 1

아 좌표가 0도 있었군요... 문제를 제대로 안읽었네요 ㅋㅋ... 감사합니다!

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

문제

문제

출처

ICPC

1퍼 입구컷 도와주세요

jshyun912 1년 전 0

jhuni 1년 전 1

jshyun912 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말