#PU1014. USACO 2020 February Contest, Silver — Problem 1. Swapity Swapity Swap

    ID: 1160 传统题 文件IO:swap 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:feb20来源:usaco.orgscoring:equal_test_cases模拟区间DP

USACO 2020 February Contest, Silver — Problem 1. Swapity Swapity Swap

USACO 2020 February Contest, Silver — Problem 1. Swapity Swapity Swap

题目描述

Farmer John's NN cows (1≤N≤1051\le N\le 10^5) are standing in a line. The iith cow

from the left has label ii for each 1≤i≤N1\le i\le N.

Farmer John has come up with a new morning exercise routine for the cows. He

has given the cows MM pairs of integers (L1,R1)…(LM,RM)(L_1,R_1) \ldots (L_M, R_M), where

1≤M≤1001 \leq M \leq 100. He then tells the cows to repeat the following MM-step

process exactly KK (1≤K≤1091\le K\le 10^9) times:

For each ii from 11 to MM:

The sequence of cows currently in positions Li…RiL_i \ldots R_i from the left

reverse their order.

After the cows have repeated this process exactly KK times, please output the

label of the iith cow from the left for each 1≤i≤N1\le i\le N.

输入格式

The first line contains NN, MM, and KK. For each 1≤i≤M1\le i\le M, line i+1i+1

line contains LiL_i and RiR_i, both integers in the range 1…N1 \ldots N, where

Li<RiL_i < R_i.

输出格式

On the iith line of output, print the iith element of the array after the

instruction string has been executed KK times.

数据范围

Test case 2 satisfies N=K=100N=K=100.

Test cases 3-5 satisfy K≤103K\le 10^3.

Test cases 6-10 satisfy no additional constraints.

样例

样例 1

7 2 2

2 5

3 7
1

2

4

3

5

7

6

Initially, the order of the cows is $[1,2,3,4,5,6,7]$ from left to right.  After

the first step of the process, the order is $[1,5,4,3,2,6,7]$. After the second

step of the process, the order is $[1,5,7,6,2,3,4]$.  Repeating both steps a

second time yields the output of the sample.

Problem credits: Brian Dean