| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 74 | 24 | 19 | 34.545% |
You are given an $N \times N$ matrix $A$.
Two types of lines exist on the matrix: rising and falling. There are $2N-1$ lines for each type, where rising lines are numbered $\mathrm{RL}_i$ and falling lines are numbered $\mathrm{FL}_i$ for each $1 \le i \le 2N-1$. The below picture illustrates the line layout when $N=5$.
You have to perform $Q$ cumulative queries in order on this matrix, which is given by the input as:
Each query specifies two line ranges of different types on the matrix, which is $\left\{ \mathrm{RL}_i \mid s_\mathrm{R} \le i \le e_\mathrm{R} \right\}$ and $\left\{ \mathrm{FL}_i \mid s_\mathrm{F} \le i \le e_\mathrm{F} \right\}$, and a value $v$. You should add the value $v$ to every element in the intersection of such range, i.e., $$\left\{ \mathrm{RL}_i \mid s_\mathrm{R} \le i \le e_\mathrm{R} \right\} \quad \cap \quad \left\{ \mathrm{FL}_i \mid s_\mathrm{F} \le i \le e_\mathrm{F} \right\}.$$
The following example illustrates the elements to update when $N=5$, $[s_\mathrm{R},e_\mathrm{R}]=[5,6]$, and $[s_\mathrm{F},e_\mathrm{F}]=[3,7]$:
Write a program to perform the queries and output the final status of the matrix $A$.
The first line of input contains a single integer, $N$, denoting the matrix size. ($1 \le N \le 1\,000$)
The next $N$ lines of input contain $N^2$ integers, where each line has $N$ space-separated integers, denoting the value of the matrix. Here, the $j$-th integer of the $i$-th line denotes $A_{ij}$. ($-10^9 \le A_{ij} \le 10^9$)
The next line contains a single integer, $Q$, denoting the query count. ($1 \le Q \le 200\,000$)
The $i$-th of the next $Q$ lines of input contain five space-separated integers: $s_\mathrm{R}$, $e_\mathrm{R}$, $s_\mathrm{F}$, $e_\mathrm{F}$, and $v$, denoting the $i$-th query explained earlier. ($1 \le s_\mathrm{R} \le e_\mathrm{R} \le 2N-1;$ $1 \le s_\mathrm{F} \le e_\mathrm{F} \le 2N-1;$ $-10^9 \le v \le 10^9$)
Output $N$ lines denoting the updated value of the matrix $A$. Each line should contain $N$ space-separated integers. The $j$-th integer of the $i$-th line should represent $A_{ij}$.
Modified constraints apply: $1 \le N \le 300;$ $1 \le Q \le 1\,000;$ also, $s_\mathbf{F}=e_\mathbf{F}=N$ for all queries.
Modified constraints apply: $1 \le N \le 300;$ $1 \le Q \le 1\,000$.
Modified constraints apply: $1 \le N \le 1\,000;$ $1 \le Q \le 10\,000$.
Original constraints apply: $1 \le N \le 1\,000;$ $1 \le Q \le 200\,000$.
5 110 120 130 140 150 210 220 230 240 250 310 320 330 340 350 410 420 430 440 450 510 520 530 540 550 2 5 6 3 7 15 2 3 4 5 24
110 144 130 140 150 210 244 230 255 250 310 320 345 355 350 410 435 445 440 450 510 520 530 540 550
This test corresponds to the Subtask 2.
(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:
University > 서강대학교 > CSE4152 문제해결프로그래밍실습 > 2024-2학기 중간고사 코딩 테스트 2번