| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 198 | 93 | 82 | 49.398% |
길이가 $N$인 수열 $a_1,a_2,\cdots ,a_N$이 있다. 처음에 모든 $a_i$는 0ドル$이다. 이때, 다음과 같은 쿼리를 사용해 수열 $a$를 변화시킬 수 있다.
$l r c$: 수열 $a$의 $l$번째부터 $r$번째까지의 값을 $c$로 바꾼다.
$Q$개의 쿼리가 주어질 때, $f(U,D,L,R)$을 ‘$U$번째부터 $D$번째까지의 쿼리를 순서대로 사용했을 때 $a_L+a_{L+1}+\cdots +a_R$의 값’으로 정의한다. $f$를 여러 번 시행할 경우, 각 시행은 서로 독립적이라 이전 $f$의 시행이 현재 $f$의 시행에 영향을 주지 않는다.
$\sum_{U=1}^Q\sum_{D=U}^Q\sum_{L=1}^N\sum_{R=L}^Nf(U,D,L,R)$을 998ドル,円 244,円 353$$(=119\times 2^{23}+1)$으로 나눈 나머지를 계산해 보자. 998ドル,円 244,円 353$은 소수이다.
첫 번째 줄에 정수 $N,ドル $Q$가 공백으로 구분되어 주어진다. $(1\leq N,Q\leq 300,円 000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 $Q$개의 쿼리가 한 줄에 하나씩 순서대로 주어진다. $i$번째 쿼리로 세 개의 정수 $l_i,ドル $r_i,ドル $c_i$이 공백으로 구분되어 주어진다. $(1\leq l_i\leq r_i\leq N;$ 0ドル\leq c_i<998,円 244,円 353)$
$\sum_{U=1}^Q\sum_{D=U}^Q\sum_{L=1}^N\sum_{R=L}^Nf(U,D,L,R)$를 998ドル,円 244,円 353$으로 나눈 나머지를 출력하시오.
2 2 1 2 1 2 2 2
14
\[\begin{align*}f(1,1,1,1)& =1\\ f(1,1,1,2)& =1+1=2\\ f(1,1,2,2)& =1\\ f(1,2,1,1)& =1\\ f(1,2,1,2)& =1+2=3\\ f(1,2,2,2)& =2\\ f(2,2,1,1)& =0\\ f(2,2,1,2)& =0+2=2\\ f(2,2,2,2)& =2\end{align*}\]
따라서, 답은 1ドル+2+たす1+たす1+たす3+たす2+たす0+たす2+たす2=わ14$가 된다.
10 10 10 10 593603443 4 9 993565789 3 8 238321270 7 8 424480868 10 10 556869540 8 10 279674600 7 8 575417117 6 8 948583421 6 6 468656456 4 10 865607491
830609277