Sequences

Điểm: 0,18 (OI)

Giới hạn thời gian: 0.38s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

UVA

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

~W.~ là ~1~ dãy các số nguyên dương. Nó có các đặc điểm sau:

Độ dài của dãy là ~1~ số lẻ: ~L= 2N + 1~
~N + 1~ số nguyên đầu tiên của dãy tạo thành ~1~ dãy tăng
~N + 1~ số nguyên cuối của dãy tạo thành ~1~ dãy giảm
Không có ~2~ số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau

Ví dụ: ~1~, ~2~, ~3~, ~4~, ~5~, ~4~, ~3~, ~2~, ~1~ là ~1~ dãy ~W~. độ dài ~9~. Tuy nhiên, dãy ~1~, ~2~, ~3~, ~4~, ~5~, ~4~, ~3~, ~2~, ~2~ không là ~1~ dãy ~W~.

Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy ~W~. có độ dài dài nhất.

Input

Dòng ~1~: số nguyên dương ~N~ (~N~ ~\le~ ~100000~), độ dài dãy số.

Dòng ~2~: ~N~ số nguyên dương ~a_{i}~ (~a_{i}~ ~\le~ ~10^{9}~).

Output

1 số nguyên dương duy nhất là độ dài dãy ~W.~ dài nhất.

Sample Input

10
1 2 3 4 5 4 3 2 1 10

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

vominhmanh10 đã bình luận lúc 31, Tháng 12, 2025, 13:35

hai bài dãy con tăng giảm ấy mà

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define IO ios::sync_with_stdio(0); cin.tie(0)
#define pb push_back
#define fast_func inline __attribute__((always_inline))
#define all(v) v.begin(), v.end()
const ll maxn = 1e6 + 5, inf = 1e18, mod = 1e9 + 7;
ll n, L[maxn], R[maxn], BIT[maxn], pos[maxn];
fast_func void add(int i, ll x) {
    for (; i <= n; i += i & -i) BIT[i] = max(BIT[i], x);
}
fast_func ll sum(int i) {
    ll res = 0;
    for (; i > 0; i -= i & -i) res = max(res, BIT[i]);
    return res;
} 
int main() {
    IO; cin >> n;
    vector<ll> a(n), b;
    for (ll &x: a) {
        cin >> x;
        b.emplace_back(x);
    }
    sort(all(b));
    for (int i = 0; i < n; ++i) pos[i] = lower_bound(all(b), a[i]) - b.begin() + 1;
    for (int i = 0; i < n; ++i) {
        L[i] = sum(pos[i] - 1) + 1;
        add(pos[i], L[i]);
    }
    memset(BIT, 0, sizeof(BIT));
    for (int i = n - 1; i >= 0; --i) {
        R[i] = sum(pos[i] - 1) + 1;
        add(pos[i], R[i]);
    }
    ll res = 0;
    for (int i = 0; i < n; ++i) res = max(res, min(L[i], R[i]) * 2 - 1);
    cout << res;
}

0

kt007 đã bình luận lúc 22, Tháng 12, 2024, 8:21

Hide: Tìm dãy con tăng/giảm (tknp)

-34

vndkhoi đã bình luận lúc 12, Tháng 6, 2023, 2:40

dp thôi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-82

kripper đã bình luận lúc 30, Tháng 3, 2023, 7:46

tao la trum

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.