Problem:


Score: 400 points

Problem Statement

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east.
A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i).
Takahashi the king is interested in the following Q matters:

The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

N is an integer between 1 and 500 (inclusive).

M is an integer between 1 and 200 \ 000 (inclusive).

Q is an integer between 1 and 100 \ 000 (inclusive).

1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)

1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

Input

Input is given from Standard Input in the following format:

N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

Output

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

Sample Input 1

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

10 3 2
1 5
2 8
7 10
1 7
3 10

Sample Output 2

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1.
The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

Sample Output 3

7
9
10
6
8
9
6
7
8
10



Sample input:
2 3 1
1 1
1 2
2 2
1 2


Sample output:
3

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(M)]
PQ = [list(map(int, input().split())) for i in range(Q)]

acc = [[0 for i in range(N+1)] for i in range(N+1)]  # acc[i][j] = i以下からスタートしてj以下で終了する電車の数
coordinate = [[0 for i in range(N)] for i in range(N)]
for l, r in LR:
    l -= 1
    r -= 1
    coordinate[l][r] += 1

for i in range(N):
    for j in range(N):
        acc[i+1][j+1] = acc[i][j+1] + acc[i+1][j] - acc[i][j] + coordinate[i][j]
print(acc)
for p, q in PQ:
    p -= 1
    ans = acc[N][q] - acc[p][q]
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int, input().split())
List1 = [[0 for i in range(n+1)] for j in range(n+1)]
List2 = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
  l,r = map(int, input().split())
  List1[l - 1][r - 1] += 1


for i in range(n):
  for j in range(n - i):
    List2[j][j + i] = List2[j + 1][j + i] + List2[j][j + i - 1] + List1[j][j + i]


for i in range(q):
  a, b = map(int, input().split())
  print(List2[a - 1][b - 1])

Submission status: Wrong Answer

Solution code:
n,m,q = map(int, input().split())
List1 = [[0 for i in range(n)] for j in range(n)]
List2 = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
  l,r = map(int, input().split())
  List1[l - 1][r - 1] += 1

for i in range(n):
  List2[i][i] += List1[i][i]
for i in range(1, n):
  for j in range(n - i):
    List2[j][j + i] = List2[j + 1][j + i] + List2[j][j + i - 1] + List1[j][j + i]


for i in range(q):
  a, b = map(int, input().split())
  print(List2[a - 1][b - 1])

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
table=[[0]*N for _ in range(N)]
for i in range(M):
    l,r=map(int,input().split())
    table[l-1][r-1]+=1
dp=[[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]-dp[i][j]+table[i][j]
for i in range(Q):
    p,q=map(int,input().split())
    a=dp[q][q]
    b=dp[p-1][q-1]
    c=dp[q-1][p-1]
    d=dp[p-1][p-1]
    print(a-b-c+d)

Submission status: Wrong Answer

Solution code:
n,m,Q = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(m)]
PQ = [list(map(int,input().split())) for _ in range(Q)]

import numpy as np
from operator import itemgetter
Line = np.array([0]*(n+1),dtype = "int32")
LR.sort(key = itemgetter(1))
PQ.sort(key = itemgetter(1))
point = 0
Ans = []
for p,q in PQ:
    for l,r in LR[point:]:
        if r > q:
            break
        else:
            point += 1
            Line[l] += 1
    Ans.append(np.sum(Line[p:q+1]))
print(*Ans,sep = "\n")

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
N,M,Q = map(int,input().split())
lr = [tuple(map(int,input().split())) for i in range(M)]
pq = [tuple(map(int,input().split())) for i in range(Q)]
lr.sort()
l = [lr[i][0] for i in range(M)]
r = [lr[i][1] for i in range(M)]

l_I = {}
for i in range(M-1,-1,-1):
    l_I[l[i]]=i
j = -1
for i in range(1,N+1):
    if i in l_I:
        j = l_I[i]
    else:
        l_I[i] = j+1

r_d = {}
for i in range(1,N+1):
    r_d[i] = r[l_I[i]:]
    r_d[i].sort()
ans = defaultdict(lambda:{})
for p in range(1,N+1):
    for q in range(p,N+1):
        ans[p][q] = bisect.bisect(r_d[p],q)
for i in range(Q):
    p,q = pq[i]
    print(ans[p][q])

Submission status: Wrong Answer

Solution code:
import bisect
from collections import defaultdict
N,M,Q = map(int,input().split())
lr = [tuple(map(int,input().split())) for i in range(M)]
pq = [tuple(map(int,input().split())) for i in range(Q)]
lr.sort()
l = [lr[i][0] for i in range(M)]
r = [lr[i][1] for i in range(M)]

l_I = {}
for i in range(M-1,-1,-1):
    l_I[l[i]]=i
j = 0
for i in range(1,N+1):
    if i in l_I:
        j = l_I[i]
    else:
        l_I[i] = j+1

r_d = {}
for i in range(1,N+1):
    r_d[i] = r[l_I[i]:]
    r_d[i].sort()
ans = defaultdict(lambda:{})
for p in range(1,N+1):
    for q in range(1,N+1):
        ans[p][q] = bisect.bisect(r_d[p],q)
for i in range(Q):
    p,q = pq[i]
    print(ans[p][q])

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m,q=map(int,input().split())
s=np.zeros((n,n))
for i in range(m):
    l,r=map(int,input().split())
    s[n-l][r-1]+=1
s=np.cumsum(np.cumsum(s,axis=0),axis=1)
print(s)
for i in range(q):
    d,t=map(int,input().split())
    print(int(s[n-d][t-1]))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = S()
    k = I()
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            quit()
    print(1)

#D
def D():
    n,m,q = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        l,r = LI()
        heappush(v[l-1],r-1)
    f = [[bisect.bisect_right(v[i],j) for j in range(n)] for i in range(n)]
    for i in range(q):
        p,q = LI()
        p -= 1
        q -= 1
        ans = 0
        for j in range(p,q+1):
            ans += f[j][q]
        print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = S()
    k = I()
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            quit()
    print(1)

#D
def D():
    n,m,q = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        l,r = LI()
        heappush(v[l-1],r-1)
    f = [[bisect.bisect_right(v[i],j) for j in range(n)] for i in range(n)]
    for i in range(q):
        p,q = LI()
        ans = 0
        p -= 1
        q -= 1
        for i in range(p,q+1):
            ans += f[i][q]
        print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = S()
    k = I()
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            quit()
    print(1)

#D
def D():
    n,m,q = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        l,r = LI()
        heappush(v[l-1],r-1)
    f = [[bisect.bisect_left(v[i],j+1) for j in range(n)] for i in range(n)]
    for i in range(q):
        p,q = LI()
        ans = 0
        p -= 1
        q -= 1
        for i in range(p,q+1):
            ans += f[i][q]
        print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
import numpy as np
LR = np.full((501,501),0)
Ans = []
for _ in range(m):
    x,y = map(int,input().split())
    LR[x][y] += 1

def portionsum(List,x,y):#List must be 2-demension,x>y
    re = 0
    for l in range(x,y+1):
        re += sum(List[l][x:y+1])
    return re

for i in range(q):
    p,q = map(int,input().split())
    Ans.append(portionsum(LR,p,q))
for _ in Ans:
    print(_)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
lr = [[0] * (n+1) for i in range(n+1)]
for _ in range(m):
    l,r=map(int,input().split())
    lr[l][r] += 1
for i in range(len(lr)):
    for j in range(len(lr[i])-1):
        lr[i][j+1] = lr[i][j]+lr[i][j+1]
pq = [list(map(int,input().split())) for _ in range(q)]

for i in range(len(pq)):
    ans=0
    for j in range(pq[i][0],pq[i][1]+1):
        ans+=lr[j][pq[i][1]]-lr[j][pq[i][0]]
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
lr = [list(map(int,input().split())) for _ in range(m)]
pq = [list(map(int,input().split())) for _ in range(q)]
lr = sorted(lr,key=lambda x:(x[0],-x[1]))
from itertools import groupby
new_lr = []
for a,g in groupby(lr,key=lambda x:x[0]):
    l = []
    for item in g:
        l.append(item)
    new_lr.append(l)

for i in range(len(pq)):
    ans = 0
    for l in new_lr:
        if l[0][0]<pq[i][0]:
            continue
        for k in range(len(l)):
            if l[k][1]<=pq[i][1]:
                ans+=len(l[k:])
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,M,Q=map(int,input().split())
LR=[[i,0] for i in range(M)]
for i in range(M):
    l,r=map(int,input().split())
    LR[i][0]=l
    LR[i][1]=r
LR.sort(key=lambda x:x[0])
pq=[[0,0] for i in range(Q)]
for i in range(Q):
    pq[i][0],pq[i][1]=map(int,input().split())
for i in range(Q):
    ans=0
    p,q=pq[i][0],pq[i][1]
    index=bisect.bisect_left(LR[:][0],p)
    if p!=LR[index][0]:
        index+=1
    for j in range(index,M):
        if LR[j][1]<=q:
            ans+=1
        elif LR[j][0]>q:
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())

res = [[0]*n for i in range(n)]
for i in range(m):
    L,r = map(int,input().split())
    L -= 1
    r -= 1
    res[r][0] += 1
    if L != n-1:
        res[r][L+1] -= 1
print(res)
for i in range(n):
    for j in range(1,n):
        res[i][j] += res[i][j-1]
for i in range(n):
    for j in range(1,n):
        res[j][i] += res[j-1][i]
print(res)
for i in range(q):
    p,q = map(int,input().split())
    print(res[q-1][p-1])

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(list(map(int,input().split())))
query = []
for i in range(Q):
  query.append(list(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]):
    ans += (grid[query[i][0]+j+1][query[i][1]]-grid[query[i][0]+j+1][query[i][0]-1])
  print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
L_R=[list(map(int,input().split())) for _ in range(M)]
P_Q=[[q]+list(map(int,input().split()))+[0] for q in range(Q)]
L_R.sort()
P_Q.sort(key=lambda x:x[1])
for i,p,q,c in P_Q:
    t=0
    for l_r in L_R:
        l=l_r[0]
        r=l_r[1]
        if(p<=l and r<=q):
            t+=1
    P_Q[i][3]=t
P_Q.sort(key=lambda x:x[0])
for a in P_Q:
    print(a[3])

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int,input().split())
src = [list(map(int,input().split())) for _ in range(M)]
query = [list(map(int,input().split())) for _ in range(Q)]
arr2 = [[0]*N for _ in range(N)]
csum2 = [[0]*N for _ in range(N)]
for l,r in src:
    l -= 1
    r -= 1
    arr2[l][r] += 1
csum2[0][0] = arr2[0][0]
for i in range(N):
    csum2[i][0] = csum2[l-1][0] + arr2[i][0]
    csum2[0][i] = csum2[0][i-1] + arr2[0][i]

for l in range(1,N):
    for r in range(1,N):
        csum2[l][r] = arr2[l][r] + csum2[l-1][r] + csum2[l][r-1] - csum2[l-1][r-1]

for p,q in query:
    p -= 1
    q -= 1
    if p == 0:
        print(csum2[q][q])
    else:
        print(csum2[q][q] - csum2[q][p-1] - csum2[p-1][q] + csum2[p-1][p-1])

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())

arr = [[0 for j in range(n)] for i in range(n)]
arr_sum = []
arr_sum2 = []

for i in range(m):
    l, r = map(int, input().split())
    arr[l-1][r-1] += 1


for i in range(n):
    s = 0
    arr_tmp = []
    for j in range(n):
            s += arr[i][j]
            arr_tmp.append(s)
    arr_sum.append(arr_tmp)


for j in range(n-1,-1,-1):
    s = 0
    arr_tmp2 = []
    for i in range(n-1,-1,-1):
            s += arr_sum[i][j]
            arr_tmp2.append(s)
    arr_sum2.append(arr_tmp2)
    
ans_arr = []
for k in range(q):
    p, q = map(int, input().split())
    ans = arr_sum2[p-1][q-1]
    ans_arr.append(ans)

for i in ans_arr:
    print(i)

Submission status: Wrong Answer

Solution code:
n,m,q= map(int,input().split())
dataList = [[0 for xIndex in range(n+1)]for yIndex in range(n+1)]

for i in range(m):
    xTemp,yTemp = map(int,input().split())
    dataList[yTemp][xTemp]+=1
pqList=[list(map(lambda x:int(x),input().split()))for i in range(q)]
print(dataList)
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex][xIndex-1]
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex-1][xIndex]
print(dataList)

for pq in pqList:
    p = pq[0]-1
    q = pq[1]
    print(dataList[q][q]+dataList[p][p]-dataList[p][q]-dataList[q][p])

Submission status: Wrong Answer

Solution code:
n,m,q= map(int,input().split())
lrList=[list(map(int,input().split()))for i in range(m)]
pqList=[list(map(int,input().split()))for i in range(q)]
for pq in pqList:
    ans = 0
    for lr in lrList:
        ans +=(pq[0] <= lr[0] and pq[1] >= lr[1])
    print(1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())

mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] = +1


def solve():

    for i in range(N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i][j-1]

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

    for i in range(1, N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i-1][j] + \
                mat[i][j-1] - mat[i-1][j-1]

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat[qr][qr] - mat[ql-1][qr] - mat[qr][ql-1] + mat[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve2()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())

mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] = 1


def solve():

    for i in range(N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i][j-1]

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

    for i in range(1, N+1):
        for j in range(1, N+1):
            mat[i][j] = mat[i][j] + mat[i-1][j] + \
                mat[i][j-1] - mat[i-1][j-1]

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat[qr][qr] - mat[ql-1][qr] - mat[qr][ql-1] + mat[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a+1)


solve2()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())

mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] = 1


def solve():

    for i in range(N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i][j-1]

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

    mat2 = [[0]*(N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            mat2[i][j] += mat[i][j] + mat2[i-1][j] + \
                mat2[i][j-1] - mat2[i-1][j-1]

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat2[qr][qr] - mat2[ql-1][qr] - mat2[qr][ql-1] + mat2[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve2()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())

mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] = 1


def solve():

    for i in range(N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i][j-1]

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

    mat2 = [[0]*(N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            mat2[i][j] = mat[i][j] + mat2[i-1][j] + \
                mat2[i][j-1] - mat2[i-1][j-1]

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat2[qr][qr] - mat2[qr][ql-1] - mat2[qr][ql-1] + mat2[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve2()

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())
trains = []
for _ in range(M):
    a, b = map(int, input().split())
    trains.append([a, b])

query = []
for _ in range(Q):
    a, b = map(int, input().split())
    query.append([a, b])


def solve():
    # i駅目以前に(i駅も含む)出発した電車
    start_acc = [0]*(N+2)
    # i駅目以前に(i駅も含む)終点を迎えた電車
    finished_acc = [0]*(N+2)

    train = sorted(trains, key=lambda x: x[0])

    # 各駅の出発・到着数をカウント
    for start, dest in train:
        start_acc[start] += 1
        finished_acc[dest] += 1

    # 累積和にする
    for i in range(1, N+2):
        start_acc[i] += start_acc[i-1]
        finished_acc[i] += finished_acc[i-1]

    # qs~qdの数 = qD(を含む)までに終わった数 - qs(を含む)までに終わったやつ - qs(を含まない)より前に出発したやつ
    ans = []
    for qs, qd in query:
        a = finished_acc[qd] - finished_acc[qs-1] - start_acc[qs-1]
        b = 0

        for start, dest in train:
            if start < qs and dest > qd:
                b += 1
        ans.append(a+b)

    return ans


ans = solve()
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())
trains = []
for _ in range(M):
    a, b = map(int, input().split())
    trains.append([a, b])

query = []
for _ in range(Q):
    a, b = map(int, input().split())
    query.append([a, b])


def solve():
    # i駅目以前に(i駅も含む)出発した電車
    start_acc = [0]*(N+2)
    # i駅目以前に(i駅も含む)終点を迎えた電車
    finished_acc = [0]*(N+2)

    train = sorted(trains, key=lambda x: x[0])

    # 各駅の出発・到着数をカウント
    for start, dest in train:
        start_acc[start] += 1
        finished_acc[dest] += 1

    # 累積和にする
    for i in range(1, N+2):
        start_acc[i] += start_acc[i-1]
        finished_acc[i] += finished_acc[i-1]

    # qs~qdの数 = qD(を含む)までに終わった数 - qs(を含む)までに終わったやつ - qs(を含まない)より前に出発したやつ
    ans = []
    for qs, qd in query:
        a = finished_acc[qd] - finished_acc[qs-1] - start_acc[qs-1]
        ans.append(a)

    return ans


ans = solve()
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]
 
#電車の数
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]

Submission status: Wrong Answer

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]

#累積和表を作る
#解説には1次元累積和を加算しても間に合うとい書いてあったが、2次元累積和でないとタイムアウトする
cumlative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]

Submission status: Wrong Answer

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
trains_cumulative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        trains_cumulative_sum[start][arrive] = trains_cumulative_sum[start][arrive - 1] + trains[start][arrive]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]
    result = 0
    #for j in range(start, arrive + 1):
    #    result += trains_cumulative_sum[j][arrive] - trains_cumulative_sum[j][start - 1]
    print(result)

Submission status: Wrong Answer

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
trains_cumulative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        trains_cumulative_sum[start][arrive] = trains_cumulative_sum[start][arrive - 1] + trains[start][arrive]

Submission status: Wrong Answer

Solution code:
from itertools import takewhile
def main():
    (n, m, q) = map(lambda x: int(x), input().split(' '))
    
    trains = []
    for i in range(m):
        (l, r) = map(lambda x: int(x), input().split(' '))
        section = r - l # n-1 .. 0 
        trains.append((section, l, r))
    trains.sort(key=lambda x: x[0])


    for i in range(q):
        (p, q) = map(lambda x: int(x), input().split(' '))
        count = 0
        for s, l, r in takewhile(lambda train: p-q<=train[0], trains):
            if l <= p and q <= r:
                count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import takewhile
def main():
    (n, m, q) = map(lambda x: int(x), input().split(' '))
    
    trains = []
    for i in range(m):
        (l, r) = map(lambda x: int(x), input().split(' '))
        section = r - l # n-1 .. 0 
        trains.append((section, l, r))
    trains.sort(key=lambda x: x[0])


    for i in range(q):
        (p, q) = map(lambda x: int(x), input().split(' '))
        count = 0
        for s, l, r in takewhile(lambda train: p-q<=train[0], trains):
            print(l, p, q, r)
            if p <= l and r <= q:
                count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())

lr = [[0 for i in range(n)] for j in range(n)]
for i in range(m) :
    l,r = map(int,input().split())    
    lr[l-1][r-1] = lr[l-1][r-1] + 1

#for l in lr :        
#    print(l)
#print()

# 二次元累積和
for i in range(n) :
    for j in range(n) :
        left = 0
        btm  = 0
        mid  = 0

        if i > 0 :
            left = lr[j][i-1]
        if j > 0 :
            btm  = lr[j-1][i]
        if i > 0 and j > 0 :
            mid  = lr[j-1][i-1]
       
        lr[j][i] = lr[j][i] + left + btm - mid

#for l in lr :        
#    print(l)

ans=[] 
for i in range(q) :
    l,r = map(int,input().split())

    l = l - 1
    r = r - 1
    pre = 0
    if l > 0:        
        pre = lr[r-1][l] + lr[l-1][r] - lr[l-1][l-1]     

    count = lr[r][r] - pre
    ans.append(count)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())

lr = [[0 for i in range(n)] for j in range(n)]
for i in range(m) :
    l,r = map(int,input().split())    
    lr[l-1][r-1] = lr[l-1][r-1] + 1

# 二次元累積和
for i in range(n) :
    for j in range(n) :
        left = 0
        btm  = 0
        mid  = 0

        if i > 0 :
            left = lr[j][i-1]
        if j > 0 :
            btm  = lr[j-1][i]
        if i > 0 and j > 0 :
            mid  = lr[j-1][i-1]
       
        lr[j][i] = lr[j][i] + left + btm - mid

#for l in lr :        
#    print(l)

ans=[] 
for i in range(q) :
    l,r = map(int,input().split())

    l = l - 1
    r = r - 1
    pre = 0
    if l > 0:        
        pre = lr[r][l] + lr[l][r] - lr[l][l]     

    count = lr[r][r] - pre
    ans.append(count)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())

lr = [[0 for i in range(n)] for j in range(n)]
for i in range(m) :
    l,r = map(int,input().split())    
    lr[l-1][r-1] = lr[l-1][r-1] + 1

# 二次元累積和
for i in range(n) :
    for j in range(n) :
        left = 0
        btm  = 0
        mid  = 0

        if i > 0 :
            left = lr[j][i-1]
        if j > 0 :
            btm  = lr[j-1][i]
        if i > 0 and j > 0 :
            mid  = lr[j-1][i-1]
       
        lr[j][i] = lr[j][i] + left + btm - mid

#for l in lr :        
#    print(l)

ans=[] 
for i in range(q) :
    p,q = map(int,input().split())

    pre = 0
    if p > 1:        
        pre = lr[q-1][p-1] + lr[p-1][q-1] - lr[p-1][p-1]     

    count = lr[q-1][q-1] - pre
    ans.append(count)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
PQ = [[int(_) for _ in input().split()] for _ in range(Q)]

cumsum = [[0] * (N+2) for _ in range(N+1)]
for lr in LR:
    cumsum[lr[0]][lr[0]] += 1
    if lr[1] < N:
        cumsum[lr[0]][lr[1]+1] -= 1
for i in range(N+1):
    for j in range(i, N):
        cumsum[i][j+1] += cumsum[i][j]
[print(_) for _ in cumsum]
for pq in PQ:
    print(sum([cumsum[i][i]-cumsum[i][pq[1]+1]
               for i in range(pq[0], pq[1]+1)]))

Submission status: Wrong Answer

Solution code:
class Train:
    def __init__(self, left, right):
        self.left = left
        self.right = right


class Question:
    def __init__(self, p, q):
        self.p = p
        self.q = q


N, M, Q = map(int, input().split())
trains = []
questions = []
for _ in range(M):
    left, right = map(int, input().split())
    trains.append(Train(left, right))
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append(Question(p, q))

m = {}
cm = {}
rm = {}
for i in range(N+1):
    for j in range(N+1):
        m.setdefault(i, {})
        m[i][j] = 0
        cm.setdefault(i, {})
        cm[i][j] = 0
        rm.setdefault(i, {})
        rm[i][j] = 0

for train in trains:
    m[train.left][train.right] += 1


for i in range(1, N+1):
    for j in range(i, N+1):
        cm[i][j] = m[i][j] + cm[i][j-1]

for i in range(N+1):
    for j in range(N+1)[::-1]:
        if j == N:
            rm[j][i] += cm[j][i]
        else:
            rm[j][i] += cm[j][i] + rm[j+1][i]

for question in questions:
    print(rm[question.p][question.q] - rm[0][question.p-1])

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())

LR = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]


for i in pq:
    cnt = 0
    for j in LR:
        if i[0]<=j[0] and i[1]>=j[1]:
            cnt += 1
    if cnt != 0:
        print(cnt)