以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 3 – Fortune Telling
占い(Fortune Telling)
K 理事長は占いが好きで,いつも様々な占いをしている.今日はカードを使って今年のIOI での日本選
手団の出来を占うことにした.
占いの方法は次のようなものである.
• まずカードを縦M 行,横N 列の長方形状に全て表にして並べる.
• i = 1, · · · , K について,「上から数えてAi 行目からBi 行目かつ,左から数えてCi 列目からDi 列目に
ある全てのカードの表裏をひっくり返す」という操作を行う.すなわち,上からa 行目で左からb 列
目にあるカードを(a, b) と書いたとき,各i について,Ai ≦a ≦Bi かつCi ≦b ≦Di をみたすカード
(a, b) を全てひっくり返す操作を行う.
• 操作が終わった後,表になっているカードの枚数によって占いの結果が出る.
K 理事長は途中でカードをひっくり返す回数があまりに多いことに気付いたので,カードを実際に使っ
て占うのはやめて,操作が終わった後に表になっているカードの枚数だけを求めることにした.
課題
行の長さM,列の長さN,操作の回数K およびK 回の操作の指示が与えられたとき,操作後に表になっ
ているカードの枚数を求めるプログラムを作成せよ.
制限
1 ≦M ≦1 000 000 000 (= 109) 行の長さ
1 ≦N ≦1 000 000 000 (= 109) 列の長さ
1 ≦K ≦100 000 (= 105) 操作の回数
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数M, N, K が空白を区切りとして書かれており,カードがM 行N 列に並んでいること
と,操作を行う回数がK 回であることを表す.
• 1 + i 行目(1 ≦i ≦K) には4 つの整数Ai, Bi,Ci, Di (1 ≦Ai ≦Bi ≦M, 1 ≦Ci ≦Di ≦N) が書かれており,
i 回目の操作は上からAi 行目からBi 行目かつ,左からCi 列目からDi 列目のカードを全てひっくり
返すことを表す.
占い– 1 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 3 – Fortune Telling
出力
標準出力に,K 回の操作後に表になっているカードの枚数を1 行で出力せよ.
採点基準
採点用データのうち,配点の30%分については,K ≦3 000 を満たす.
入出力例
入力例1 出力例1
6 5 3 11
2 4 1 4
4 6 3 5
1 2 3 5
この例では,K = 3 回の操作は以下のように行われる.
表のカードを□,裏のカードを■で表すと,
初期状態
□□□□□
□□□□□
□□□□□
□□□□□
□□□□□
□□□□□
↓
□□□□□
■■■■□
■■■■□
■■■■□
□□□□□
□□□□□
↓
□□□□□
■■■■□
■■■■□
■■□□■
□□■■■
□□■■■
占い– 2 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 3 – Fortune Telling
↓
□□■■■
■■□□■
■■■■□
■■□□■
□□■■■
□□■■■
最終状態
最終状態で表になっているカードの枚数11 を出力する.
占い– 3 / 3