Submission #960391

#	Time	Username	Problem	Language	Result	Execution time	Memory
960391		vjudge1	Financial Report (JOI21_financial)	C++17	100 / 100	301 ms	31384 KiB

Main

#include <bits/stdc++.h>
#define Y8o "Financial Report"
#define maxn 300005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof()
{
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime()
{
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, D;
int a[maxn], lef[maxn], dp[maxn];
pii b[maxn];
set<int> s;

/// dsu
int root[maxn], sz[maxn], mx[maxn];
int get(int x)
{
    return x == root[x] ? x : root[x] = get(root[x]);
}
void uni(int u, int v)
{
    int p = get(u), q = get(v);
    if(p != q)
    {
        if(sz[p] < sz[q]) swap(p, q);
        root[q] = p, sz[p] += sz[q], mx[p] = max(mx[p], mx[q]);
    }
}

void prepare()
{
    sort(b + 1, b + n + 1, [](pii x, pii y) { return x.first == y.first ? x.second < y.second : x.first > y.first; });

    for(int i = 1; i <= n; i ++)
    {
        int val = b[i].first, pos = b[i].second;

        if(!s.size()) lef[pos] = 1;
        else
        {
            auto it = s.lower_bound(pos);
            if(it == s.begin()) lef[pos] = 1;
            else
            {
                it --;
                lef[pos] = *it + 1;
            }
        }

        if(pos >= 2 && a[pos - 1] >= a[pos]) uni(pos, pos - 1);
        if(pos < n && a[pos] < a[pos + 1]) uni(pos, pos + 1);

        int p = get(pos);
        if(sz[p] >= D) s.insert(mx[p]);
    }
}

int st[4 * maxn];
void update(int i, int val, int id = 1, int l = 1, int r = n)
{
    if(i < l || r < i) return ;
    if(l == r) { st[id] = val; return; }

    int mid = (l + r) >> 1;
    update(i, val, id * 2, l, mid), update(i, val, id * 2 + 1, mid + 1, r);

    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get2(int u, int v, int id = 1, int l = 1, int r = n)
{
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[id];
    int mid = (l + r) >> 1;
    return max( get2(u, v, id * 2, l, mid), get2(u, v, id * 2 + 1, mid + 1, r) );
}

void solve()
{
    cin >> n >> D;
    for(int i = 1; i <= n; i ++) cin >> a[i], b[i] = { a[i], i };
    for(int i = 1; i <= n; i ++) root[i] = i, sz[i] = 1, mx[i] = i;

    prepare();

    sort(b + 1, b + n + 1);
    vector<int> store;

    for(int i = 1; i <= n; i ++)
    {
        int val = b[i].first, pos = b[i].second;
        if(store.size() && val != a[ store.back() ])
        {
            for(int x : store) update(x, dp[x]);
            store.clear();
        }

        dp[pos] = lef[pos] <= pos - 1 ? get2(lef[pos], pos - 1) + 1 : 1;
        store.push_back(pos);
    }

    int ans = 0;
    for(int i = 1; i <= n; i ++) ans = max(ans, dp[i]);

    cout << ans;
}

/// Ý tưởng: giả sử dãy ta tìm đc là k1, k2, k3, ... kx
/// --> đưa về bài toán tìm dãy con tăng dài nhất thỏa mãn giữa k(i) đến được k(i - 1) với i >= 2
/// tức giống kiểu xét tổng quát là với i, j,  để j đến đc i <=> tồn tại cách j nhảy độ dài <= K vào các
/// số < a[j] và đến được i.
int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --)
    {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void prepare()':
Main.cpp:58:13: warning: unused variable 'val' [-Wunused-variable]
   58 |         int val = b[i].first, pos = b[i].second;
      |             ^~~
Main.cpp: In function 'void iof()':
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35