ただのメモ

他の人に見せても良い方のメモ

Competitive Programing Typical 90 Problem day17

Day 17.

There are 3 types of solutions.

1st code is below.

 

#1st solution

n, M = map(int,input().split())
lr = 
for i in range(M):
  l,r = map(int,input().split())
  lr.append((l,r))

answer = 0
for i in range(M-1):
  a, b = lr[i]
  for j in range(i+1,M):
    c,d = lr[j]
    if a<c<b<d or c<a<d<b:
      answer += 1
print(answer)

 

2nd code is below.

 

#2nd solution
n, m = map(int,input().split())
lr = 
cnt = [0]*n
cntl = [0]*n
cntr = [0]*n
posr = [ for j in range(n)]
for i in range(m):
  l,r = map(int,input().split())
  lr.append((l,r))
  cnt[l-1]+= 1
  cnt[r-1]+= 1
  cntl[l-1]+= 1
  cntr[r-1]+= 1
  posr[r-1].append(l-1)

cntrs = cntr[:1] + [0]*(n-1)
for i in range(n-1):
  cntrs[i+1] = cntrs[i] + cntr[i+1]

ans1 = 0
for i in range(n):
  ans1 += cnt[i]*(cnt[i]-1)//2

ans2 = 0
for i in range(n):
  if i > 0:
    ans2 += cntl[i] * cntrs[i-1]

ans3 = 0
weight = [0]*n
for i in range(n):
  for j in posr[i]:
    for k in range(j+1,n):  
      ans3 += weight[k]
  for j in posr[i]:
    weight[j] += 1

print(m*(m-1)//2 - ans1-ans2-ans3)

 

3rd code is below.

n, m = map(int,input().split())

class BIT:
  def __init__(selfn):
    self.size = n
    self.tree = [0] * (n+1)

  def sum(selfi):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i&-i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i&-i

bitl= BIT(n+2)
bitr = BIT(n+2)
  
lr = 
for i in range(m):
  l,r = map(int,input().split())
  lr.append*1

lr.sort(key = lambda x :(x[1],-x[0]))

ans = 0
for l,in lr:
  ans += bitl.sum(l-1)-bitr.sum(l)
  bitl.add(l,1)
  bitr.add(r,1)
print(ans)
  • express conditions in equation
  • thinking of complementary event
    • because in some cases, it it easy to classify or calculate.
  • using Binary Indexed Tree.
    • to successively calculate and memorize information quickly
      • adding some value on element of arrays
      • summation of some area of arrays
  • As I said in the past blog, Order is really important thing when we want to apply some algorithm.
  • This last solution is somehow greedy.
    • Maybe, the problem using 1 array is related to the some order.
      • but it is hard to understand what kind of order it (data) follows.

Bye! 

 

 

 

 

 

 

 

 

 

 

 

*1:l,r