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__(self, n):
self.size = n
self.tree = [0] * (n+1)
def sum(self, i):
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,r 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.
- 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.
- Maybe, the problem using 1 array is related to the some order.
Bye!
*1:l,r