Submission #985032

#	Time	Username	Problem	Language	Result	Execution time	Memory
985032		SyedSohaib_123	Strange Device (APIO19_strange_device)	Pypy 3	0 / 100	47 ms	18332 KiB

strange_device

from math import gcd
def solve():
    n,a,b=map(int,input().split())
    ls=[]
    for i in range(n):
        x,y=map(int,input().split())
        ls.append([x,y])
    a/=gcd(a,b+1)
    a*=b
    for i in ls:
        if i[1]-i[0]+1>=a:
            print(a)
            return
    q=[]
    for i in ls:
        f=i[0]%a
        s=i[1]%a
        if(f<s or i[0]==i[1]):
            q.append([f,s])
        else:
            q.append([f,a-1])
            q.append([0,s])
    q.sort()
    ans=a-q[0][0]
    maxi=q[0][1]
    for i in range(1,len(q)):
        if q[i-1][1]<q[i][0]:
            ans-=q[i][0]-q[i-1][1]-1
        maxi=max(maxi,q[i][1])
    print(int(ans-a+maxi+1))
solve()

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30