trang chủ / đề bài / icpc26_mb_a

Dạng sóng tín hiệu

Đề bài

Mô tả

Trong một sứ mệnh liên sao nhằm giải mã các tín hiệu phát sóng của người ngoài hành tinh, Tiến sĩ Aurel đã thu được một tín hiệu năng lượng được biểu diễn bằng một mảng gồm K số nguyên dương V=(V1,V2,…,VK), trong đó Vi là mức tần số tại chỉ số i (1≤i≤K). Ta định nghĩa compress(V) là dãy thu được bằng cách gộp các phần tử giống nhau liên tiếp thành một phần tử duy nhất. Ví dụ, nếu V=(1,1,2,2,2,4,3,3,1,1) thì compress(V)=(1,2,4,3,1).

Một phần tử của một dãy là cực đại địa phương chặt nếu giá trị của nó lớn hơn hẳn tất cả các phần tử kề với nó. Nó là cực tiểu địa phương chặt nếu giá trị của nó nhỏ hơn hẳn tất cả các phần tử kề với nó. Các phần tử ở biên của một dãy có độ dài ≥2 chỉ có một phần tử kề. Trong một dãy có độ dài 1, phần tử duy nhất đồng thời vừa là cực tiểu địa phương vừa là cực đại địa phương.

Cho một bản ghi tín hiệu gốc A=(A1,A2,…,AN) gồm N số nguyên dương. Một đoạn con liên tiếp S=(AL,AL+1,…,AR) với 1≤L<R≤N được gọi là một sóng rắn khi và chỉ khi mọi vị trí trong compress(S) đều là cực tiểu địa phương chặt hoặc cực đại địa phương chặt.

Yêu cầu: Hãy đếm số cặp (L,R) với 1≤L<R≤N sao cho đoạn con S là một sóng rắn.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên N (1≤N≤200000).
  • Dòng thứ hai chứa N số nguyên dương A1,A2,…,AN cách nhau bởi dấu cách (1≤Ai≤109).

Dữ liệu ra

In ra một số nguyên duy nhất: số cặp (L,R) hợp lệ.

Ràng buộc

  • 1≤N≤200000.
  • 1≤Ai≤109.

Ví dụ

Input Output Giải thích
6
1 2 4 4 3 3
11 Các cặp hợp lệ là (1,2), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (5,6), tổng cộng 11 cặp. Chẳng hạn (1,3) không hợp lệ vì trong (1,2,4) phần tử 2 không phải cực trị; (3,4) hợp lệ vì compress(4,4)=(4) có độ dài 1.
7
5 5 1 3 3 4 2
15 Ví dụ bổ sung (không có trong đề gốc). Có 21 cặp (L,R). Đoạn con hỏng khi compress(S) chứa 1,3,4 liền nhau (phần tử 3 không phải cực trị), tức là L≤3 và R≥6: có 3·2=6 cặp như vậy. Đáp án là 21−6=15.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0