페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6123

포스터 3s 1024MB

문제

깊숙한 비밀 기지에는 직사각형 포스터들이 많이 붙어 있는 벽이 있다. 포스터들은 매우 희귀하기 때문에 겹치지 않게 배치되어 있다.

가끔 벽에 붙일 가치가 있는 새로운 포스터들이 도착한다. 수호자들은 새로운 포스터들을 어디에 붙일지 결정해야 한다. 이것은 복잡한 과정이며, 당신은 그 과정의 한 단계를 돕기 위해 왔다.

수호자들은 현재 포스터들의 후보 위치를 고르고 있다. 당신은 주어진 위치에 새로운 포스터를 붙였을 때, 현재 걸려 있는 포스터들의 면적 중 가려지는 부분의 총 면적을 빠르게 계산해야 한다.

평면에 있는 n개의 서로 겹치지 않는 회색 직사각형들의 정보가 주어진다. 다음과 같은 형태의 q개의 쿼리에 답해야 한다: 주어진 직사각형 안에 있는 회색 영역의 총 면적은 얼마인가? 새로운 포스터를 실제로 붙이지는 않는다.


입력

첫 줄에는 다섯 개의 숫자, r,c,n,q,m (1≤r,c<m≤10^9+9, 0≤n,q≤50 000), 벽의 높이와 너비, 벽에 붙은 포스터의 수, 쿼리의 수, 쿼리를 계산하기 위한 모듈러 값이 주어진다. (아래에서 자세히 설명할 것이다.)

다음 n개의 줄에는 네 개의 숫자 x_1,y_1,x_2,y_2​ (0≤x_1,x_2≤r, 0≤y_1,y_2≤c) 벽에 붙어있는 직사각형 포스터의 두 대각선의 끝점의 좌표가 주어진다.

마지막 q개의 줄에는 다섯 개의 숫자 x_1′,y_1′,x_2′,y_2′,v 각각 0과 m−1 사이의 값이 주어진다. 아래의 공식을 사용하여 실제 좌표 x_1,y_1,x_2,y_2를 계산할 수 있다.

마지막 쿼리에 대한 답을 l이라고 하자 (첫 번째 쿼리에 대해서는 l=0이다). 그러면

  • x_i=(x_i′+l⋅v)(mod\ m)

  • y_i=(y_i′+l⋅v)(mod\ m)

디코딩된 좌표 x_1,y_1,x_2,y_2​는 다음 조건을 만족한다: 0≤x_1,x_2≤r, 0≤y_1,y_2≤c.


출력

각 쿼리에 대해 한 줄에 하나씩 답을 출력한다.


부분문제

번호 점수 조건
#110점

  • r, c, n, q \leq 500

  • v=0

#210점

  • r, c, n, q \leq 5000

  • v=0

#340점

  • r, c \leq 300\ 000

  • n, q \leq 50000

  • v=0

#410점

  • r \leq 10^9

  • c\leq 200\ 000

  • n, q \leq 50000

  • v=0

#510점

  • r,c \leq 10^9

  • n, q \leq 50000

  • v=0

#610점

  • r,c \leq 100\ 002

  • n, q \leq 50000

#710점

  • 추가 제한 조건이 없다.


예제 #1

8 11 3 4 13
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8 0
2 2 4 3 0
3 4 6 7 0
2 9 3 10 0
24
2
6
0

예제 #2

8 11 3 4 13
1 1 5 5
7 7 5 4
4 6 2 7
1 1 7 8 4
6 6 8 7 2
2 3 5 6 7
11 5 12 6 5
24
2
6
0

예제 1과 같은 입력이지만, 온라인 쿼리를 사용한 것이다.


출처

CPSPC 2017
로그인해야 코드를 작성할 수 있어요.