F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4534. -- 基础排序算法练习题

4534: 基础排序算法练习题

Time Limit: 12 Sec  Memory Limit: 512 MB
Submit: 236  Solved: 83
[Submit][Status][Discuss]

Description

OI小园丁ZZX最近在XJOI上夜以继日地学习编程基础知识,刷初级训练题库。在无压力AC圆的周长与面积二位数加法口算训练程序等题之后,他遇到了这样一道难题:

输入n个数a[1], a[2], ..., a[n],请将它们升序排序后输出。

ZZX苦思冥想,不知所措,便去请教德高望重的OI老司机JRY

JRY贴给他一段超自然的神秘代码,说:

你把这段东西塞进程序里,然后每次调用magic(left, right)这个函数,它就会用O(1)时间将a[left], a[left+1], ..., a[right]原地升序排序。

劲啊

但是啊由于一些奇怪的原因,你不能直接调用magic(1,n),否则程序会RE

wori?

不过这难不倒聪明伶俐的ZZX。经过一番思索,他写出了这样一段程序:

input(a[1], a[2], ..., a[n]);

magic(left_1, right_1);

magic(left_2, right_2);

...

magic(left_m, right_m);

output(a[1], a[2], ..., a[n]);

JRY看了这段代码,批判道:Native! 看我用遗传算法造个数据分分钟把你卡掉

然而ZZX并不信服,他打算把程序交到XJOI上,用评测结果来打JRY的脸。

由于XJOI管理员Ginger最近忙于打Geometry Dash,没有工夫来修理狗带了的评测姬。因此评测任务落到了你的头上。

这道题共有q个测试点。你需要对于每一个测试点,判断ZZX的程序是否输出了正确的排序结果。

Input

第一行三个整数n, m, q。
接下来m行按顺序给出了ZZX的程序中每条指令的参数left_i, right_i。
接下来q行,每行表示一个测试点,包含空格隔开的n个非负整数a[1], a[2], ..., a[n]。
1 ≤ n ≤ 1500 , 1 ≤ m ≤ 1000000 , 1 ≤ q ≤ 1500; 
1 ≤ left_i ≤ right_i ≤ n, right_i - left_i + 1 < n; 0 ≤ a[i] ≤ 1500。

Output

对于每个测试点输出一行,如果ZZX的程序能将这个数列正确排序,输出"AC",否则输出"WA"。

Sample Input

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

Sample Output

AC
WA
样例说明
对于第一个测试点:
4 2 2 3 0 7 -> [2 2 4] 3 0 7 -> 2 2 [0 3 4 7] -> [0 2 2] 3 4 7,正确。
对于第二个测试点:
5 3 8 2 1 9 -> [3 5 8] 2 1 9 -> 3 5 [1 2 8 9] -> [1 3 5] 2 8 9,错误。

HINT

Source

By Jcvb

[Submit][Status][Discuss]

HOME Back