Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCTEST18 - Quay dãy

Cho dãy số gồm N số nguyên dương đánh số vị trí từ 1 tới N. Tất cả các phần tử có giá trị khác nhau và có giá trị trong đoạn từ 1 tới N. Chọn một dãy con liên tiếp, và thực hiện các phép quay. Một phép quay trái là chuyển 1 phần tử ở đầu dãy con xuống cuối dãy con. Một phép quay phải là chuyển 1 phần tử ở cuối dãy con lên đầu dãy con. Ví dụ: Nếu dãy con được chọn là (5,1,8,3), khi thực hiện một phép quay trái ta được dãy (1,8,3,5), tương tự, thực hiện một phép quay phải ta được dãy (3,5,1,8).

Có 3 loại truy vấn:

Loại

Thực hiện

Kí hiệu

1

Chọn dãy con liên tiếp từ vị trí a tới b và quay trái k lần

L a b k

2

Chọn dãy con liên tiếp từ vị trí a tới b và quay phải k lần

R a b k

3

Trả về giá trị phần tử ở vị trí x của dãy.

P x

Ràng buộc:

-          Loại 1 và 2:  1 ≤ a < b ≤ N, và 1 ≤ k < b – a + 1.

-          Loại 3: 1 ≤ x ≤ N.

Dữ liệu:

-          Dòng 1: Hai số nguyên N (2 ≤ N ≤ 100 000) và Q (1 ≤ Q ≤ 100 000) cách nhau bởi dấu cách, lần lượt là số phần tử của dãy và số truy vấn.

-          Dòng 2: N số nguyên dương cách nhau bởi dấu cách, là dãy số ban đầu.

-          Q dòng sau: Mỗi dòng là một truy vấn mô tả như trên.

Kết quả:

-          Với mỗi truy vấn loại 3, trả về giá trị phần tử ở vị trí x của dãy trên một dòng.

Thang điểm:

-          10% bộ test: N, Q  ≤  1000 : tất cả truy vấn loại 3 ở sau tất cả truy vấn loại 1 và 2. 

-          10% bộ test: N ≤ 100 000, Q ≤ 1000 : tất cả truy vấn loại 3 ở sau tất cả truy vấn loại 1 và 2. 

-          50% bộ test: N ≤ 100 000, Q ≤ 100 000:tất cả truy vấn loại 3 ở sau tất cả truy vấn loại 1 và 2 

-          30% bộ test còn lại: N ≤ 100 000, Q ≤ 100 000. 

Ví dụ:

INPUT

OUTPUT

7 5

7 5 3 1 4 2 6

L 1 3 2

R 2 4 1

P 1

P 4

P 7

3

5

6

Giải thích:

Dãy ban đầu:      7 5 3 1 4 2 6

L 1 3 2      ->   3 7 5 1 4 2 6 

R 2 4 1      ->   3 1 7 5 4 2 6  

P 1 -> Phần tử ở vị trí 1 là: 3

P 4 -> Phần tử ở vị trí 4 là: 5 

P 7 -> Phần tử ở vị trí 7 là: 6

INPUT

OUTPUT

5 5

3 5 4 2 1

R 3 5 1

R 1 4 1

P 1

R 1 5 4

P 1

4

3

Giải thích:

Dãy ban đầu:      3 5 4 2 1

R 3 5 1        -> 3 5 1 4 2

R 1 4 1        -> 4 3 5 1 2

P 1 -> Phần tử ở vị trí 1 là : 4

R 1 5 4        -> 3 5 1 2 4

P 1 -> Phần tử ở vị trí 1 là: 3


ID RESULT TIME
code...



Được gửi lên bởi:Admin
Ngày:2011-11-17
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.