This was my source code:
from sys import stdin, stdout, stderr
def get_int():
return int(stdin.readline())
def get_ints():
return tuple(int(z) for z in stdin.readline().split())
# Quickly calculate cumulative sums of a sequence
# And quickly increment or decrement individual elements of it
class seq:
def __init__(self, n):
self.n = n
self.a = [0] * (n + 1)
def inc(self, i, j):
while i <= self.n:
self.a[i] += j
i += (i & -i)
def cumul(self, i):
tot = 0
while i > 0:
tot += self.a[i]
i -= (i & -i)
return tot
class SpecialSet:
def __init__(self, n):
self.n = n
self.abv = seq(n+2)
self.abv.inc(1, n+2)
self.blw = seq(n+2)
self.blw.inc(1, 1)
def remove(self,k):
b = self.blw.cumul(k)
dif = self.abv.cumul(b) - k
self.abv.inc(b, dif)
self.abv.inc(k, -dif)
a = self.abv.cumul(k)
dif = self.blw.cumul(a) - k
self.blw.inc(a + 1, -dif)
self.blw.inc(k + 1, dif)
def add(self, k):
b = self.blw.cumul(k)
dif = self.abv.cumul(b) - k
self.abv.inc(b, -dif)
self.abv.inc(k, dif)
a = self.abv.cumul(k)
dif = self.blw.cumul(a) - k
self.blw.inc(a + 1, dif)
self.blw.inc(k + 1, -dif)
def above(self, k):
return self.abv.cumul(k)
def below(self, k):
return self.blw.cumul(k)
def scr(i, lE, hE, tL, tH):
return max(tH-i,0)*max(min(i,lE)-tL,0) +
max(tH-max(hE,i),0)*max(i-max(lE,tL),0)
other = {'C':'D','D':'C'}
for cn in xrange(1,1+get_int()):
(N,K) = get_ints()
cs = get_ints()
ds = get_ints()
swords = [(cs[i],i+2,'C') for i in xrange(N)]+[(ds[i],i+2,'D') for i in
xrange(N)]
swords.sort()
stillValid = {}
stillValid['C'] = SpecialSet(N)
stillValid['D'] = SpecialSet(N)
tooGood = {}
tooGood['C'] = SpecialSet(N)
tooGood['D'] = SpecialSet(N)
w = 2 * N - 1
w2 = 2 * N - 1
tot = 0
while w >= 0:
(str, indx, p) = swords[w]
# sword is valid
stillValid[p].add(indx)
# remove swords that aare stronger than K + str
while swords[w2][0] > K + str:
tooGood[swords[w2][2]].add(swords[w2][1])
w2 -= 1
# count the number of ranges that:
# (i) do not include any too good sword
tooHigh = min(tooGood[q].above(indx-1) for q in 'CD')
tooLow = max(tooGood[q].below(indx+1) for q in 'CD')
# (ii) do not include any other still valid sword for p
tooHigh = min(tooHigh, stillValid[p].above(indx))
tooLow = max(tooLow, stillValid[p].below(indx))
# (iii) do include a still valid sword for otherp
otherp = other[p]
highEnough = stillValid[otherp].above(indx-1)
lowEnough = stillValid[otherp].below(indx+1)
sc = scr(indx, lowEnough, highEnough, tooLow, tooHigh)
tot += sc
w -= 1
print "Case #{}: {}".format(cn, tot)
if (cn == -1):
break
On Tue, Apr 30, 2019 at 3:09 PM Luke Pebody <l...@pebody.org> wrote:
> Also, no the problems are not specifically tested to be solvable in Python
>
> On Tue, 30 Apr 2019, 3:08 pm Luke Pebody, <l...@pebody.org> wrote:
>
>> I did Problem C large in Python
>>
>> On Tue, 30 Apr 2019, 3:05 pm Alex Wice, <alexw...@gmail.com> wrote:
>>
>>> In 2019 round 1B, problem C large doesn't seem to be possible with Pypy.
>>> If this is true, are the problems not specifically tested to be possible
>>> with Python?
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Google Code Jam" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to google-code+unsubscr...@googlegroups.com.
>>> To post to this group, send email to google-code@googlegroups.com.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/google-code/720185a5-eddf-4977-8058-377f23c5574f%40googlegroups.com
>>> .
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAECKw-O-x-HhfcsfKx9swsF-ixm3HC3ZKWN65DFTN4iThoBqAA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
