제출 #844828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844828		hbg1345	쌍둥이 독수리 (GA7_twineagles)	Pypy 2	0 / 100	22 ms	20200 KiB

twineagles

from collections import deque, defaultdict
from math import ceil, log, asin, acos, cos, sin, tan, atan2, floor, gcd, sqrt, pi
# from math import *
from heapq import *
from bisect import bisect, bisect_left
import sys
from itertools import combinations, permutations, count
from functools import lru_cache, cmp_to_key
from operator import add, mul, sub, xor
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 4) 

INF = 10 ** 20

# atan2(y, x) :=
# artan(y/x) ([-pi, pi] -> if theta < 0 -> theta += 2pi -> [0, 2pi])

def cceil(m, n):
    if n == 0:
        return INF
    return (m + n - 1) // n


class MultiList():
    BOX_RATIO = 50
    REBUILD_RATIO = 170

    def __init__(self, a=[]):
        a = list(a)
        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
            # a = sorted(list(set(a))) unique
            a.sort()
        self.build(a)

    def build(self, a=None):
        if a is None:
            a = list(self)
        # total number of elements
        N = self.size = len(a)
        # root (N/ 50)
        boxNum = int(ceil(sqrt(N / self.BOX_RATIO)))
        self.a = [a[N * i // boxNum: N * (i + 1) // boxNum] for i in range(boxNum)]

    def __len__(self):
        return self.size
    
    def __reversed__(self):
        for box in reversed(self.a):
            for e in reversed(box):
                yield e

    def __str__(self):
        return str(list(self))

    def __iter__(self):
        for box in self.a:
            for e in box:
                yield e

    def whatBox(self, x):
        for box in self.a:
            if box[-1] >= x:
                return box
        return box

    def insert(self, x):
        if len(self) == 0:
            self.a = [[x]]
            self.size = 1
            return True
        box = self.whatBox(x)
        i = bisect_left(box, x)
        '''
        # unique
        if i != len(box) and box[i] == x:
            return False
        '''
        box.insert(i, x)
        self.size += 1
        if len(box) > len(self.a) * self.REBUILD_RATIO:
            self.build()
        return True

    def remove(self, x):
        if len(self) == 0:
            return False
        box = self.whatBox(x)
        i = bisect_left(box, x)
        if i == len(box) or box[i] != x:
            return False
        y = box.pop(i)
        self.size -= 1
        if len(box) == 0:
            self.build()
        return y

    def pop(self, idx=-1):
        return self.remove(self[idx])

    def __getitem__(self, idx):
        if idx < 0:
            idx += len(self)
        if idx < 0:
            raise IndexError
        for box in self.a:
            if idx < len(box):
                return box[idx]
            idx -= len(box)
        raise IndexError

    def __contatins__(self, x):
        idx = self.lowerBound(x)
        if idx == len(self) or self[idx] != x:
            return False
        return True

    def lowerBound(self, x):
        idx = 0
        for box in self.a:
            if box[-1] >= x:
                idx += bisect_left(box, x)
                return idx
                idx += len(box)
        return len(self)

    def upperBound(self, x):
        idx = 0
        for box in self.a:
            if box[-1] > x:
                idx += bisect(box, x)
                return idx
            idx += len(box)
        return len(self)


class BIT:
    # 1 based index
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (self.N + 1)

    def addV(self, idx, v):
        while idx <= self.N:
            self.tree[idx] += v
            idx += idx & -idx
        return

    def query(self, idx):
        ret = 0
        while idx > 0:
            ret += self.tree[idx]
            idx -= idx & -idx
        return ret

    def pSum(self, i, j):
        # [i, j]의 구간 합을 return
        return self.query(j) - self.query(i - 1)



class SegTree:
    def __init__(self, op, e, n, v=None):
        # op: 연산자
        # e: 기본 값 (연산자의 항등원)
        # n: 배열의 길이
        # v: 배열
        # 0_based index
        self._n = n
        self._op = op
        self._e = e
        self._log = (n - 1).bit_length()
        # 2**k > N - 1 = > 2 ** k >= N
        self._size = 1 << self._log 
        self._d = [self._e] * (self._size << 1)
        if v is not None:
            for i in range(self._n):
                self._d[self._size + i] = v[i]
            for i in range(self._size - 1, 0, -1):
                # reverse order init
                self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1])

    def set(self, p, x):
        p += self._size
        self._d[p] = x
        while p:
            self._d[p >> 1] = self._op(self._d[p], self._d[p ^ 1])
            p >>= 1

    def get(self, p):
        return self._d[p + self._size]

    def query(self, l, r):
        # [l, r] 구간에 대한 쿼리
        return self._query(l, r + 1)

    def _query(self, l, r):
        # 구간 쿼리가 [l, r)의 형태임을 주의

        sml, smr = self._e, self._e
        l += self._size
        r += self._size
        while l < r:
            if l & 1:
                # l이 우측 자식인 경우, d[l] node를 연산에 넣어주고 l을 옮김 그 오른쪽으로 옮김
                # 왼쪽 자식인 경우에는 d[l]의 부모 노드를 쓰면 되기 때문에 넘어감
                sml = self._op(sml, self._d[l])
                l += 1
            if r & 1:
                # [x, r - 1]만 보면 되기 때문에 d[r - 1]을 참조함
                # r이 왼쪽 노드라면 올라가면서 r이 시작값으로 고정이 되기 때문에 그 r - 1까지의 값을 더 큰 노드에서 찾을 수 있다.
                # 따라서 d[r - 1]을 굳이 참조할 필요가 없음
                r -= 1
                smr = self._op(self._d[r], smr)
            l >>= 1
            r >>= 1
        return self._op(sml, smr)

    def all_query(self):
        return self._d[1]


MOD = 998244353
D, A, B, a, b = map(int, input().split())

def f(A, B, a, b):
    ret = 0
    t1 = max(0, cceil(A - 2*D, 2*D - a))
    k = A + t1*a - 2*D*(t1 + 1)
    B += t1*b
    if k <= -D:
        B -= D
        if B <= 0:
            return t1 + 1
        B += b
    if B > 0:
        t2 = max(0, cceil(B - 2*D, 2*D-b))
        return t1 + t2 + 2
    
ret = min(f(A, B, a, b), f(B, A, b, a))
print(ret)

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 48