Đếm nghịch thế

View as PDF
Submit solution
Problem ID: mininv
Points: 3.2 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Author:
hoangphat120805
Problem type

Mèo ~Capoo~ rất thích làm việc với mảng và những con số. Do dó, trong ngày sinh nhật sắp tới của mèo ~Capoo~, mọi người đã chuẩn bị một dãy số ~a_1, a_2, a_3, ..., a_n~.

Mèo ~Capoo~ không thích các cặp số nghịch thế xuất hiện trong dãy số. Vì thế, để làm cho mèo ~Capoo~ cảm thấy hạnh phúc trong ngày sinh nhật thì cần giảm số cặp nghịch thế xuống mức tối thiểu bằng cách nhân một số phần tử trong dãy cho ~-1~ hoặc giữ nguyên dãy ban đầu. Vì thời gian gấp rút nên các bạn mèo của ~Capoo~ cần sự hỗ trợ, bạn hãy giúp các bạn mèo giải quyết vấn đề này nhé!

Một nghịch thế trong dãy ~a_1, a_2, a_3, ..., a_n~ là một cặp số ~i, j~ ~(1 \le i \lt j \le n)~ sao cho ~a_i \gt a_j~.

Dữ liệu vào

  • Dòng thứ nhất chứa số nguyên dương ~n~ ~(n \le 10^5)~.
  • Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, ..., a_n~ ~(|a_i| \le 10^5)~.

Dữ liệu ra

In ra màn hình số cặp nghịch thế tối thiểu có trong dãy.

Ràng buộc

Subtask ~1~ ~(30\%)~: ~1 \le n \le 15~.

Subtask ~2~ ~(30\%)~: ~15 \le n \le 5000~.

Subtask ~3~ ~(40\%)~: ~5000 \le n \le 100000~.

Ví dụ 1

Dữ liệu
3
-8 7 2
Kết quả
0
Giải thích

Dãy số có thể viết lại thành: -8 -7 2

Ví dụ 2

Dữ liệu
6
16 -24 -64 8 48 48
Kết quả
3
Giải thích

Dãy số có thể giữ nguyên.


Comments

Please read the guidelines before commenting.


  • 0
    CPDISCIPLINE  commented on July 22, 2023, 10:01 p.m.

    Dạ bài này có trên codeforces không ạ. Nếu có cho em xin nguồn với ạ