Submission #885707

#	Time	Username	Problem	Language	Result	Execution time	Memory
885707		12345678	Financial Report (JOI21_financial)	C++17	100 / 100	749 ms	59584 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;

int n, d, v[nx], l[nx], off[nx], t, res, ans;
set<pair<int, int>> s;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
priority_queue<pair<int, int>> p;
vector<int> ed[nx];
map<int, int> mp;

struct segtree
{
    int d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=vl==0?0:max(d[i], vl));
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} st;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>d;
    for (int i=1; i<=n; i++) cin>>v[i], l[i]=n, mp[v[i]]=0;
    for (auto &[x, y]:mp) y=++t;
    for (int i=n; i>=1; i--)
    {
        while (!pq.empty()&&pq.top().second>i+d) pq.pop();
        if (pq.size()>=d)
        {
            auto itr=s.insert(make_pair(pq.top().first, -i));
            while ((*s.begin())!=make_pair(pq.top().first, -i)) s.erase(s.begin());
        }
        auto itr=s.upper_bound(make_pair(v[i], INT_MAX));
        if (itr!=s.end()) l[i]=-itr->second;
        ed[min(l[i]+d, n)].push_back(i);
        pq.push({v[i], i});
    }
    for (int i=1; i<=n; i++)
    {
        res=st.query(1, n, 1, 1, mp[v[i]]-1)+1;
        if (l[i]==n) ans=max(ans, res);
        st.update(1, n, 1, mp[v[i]], res);
        for (auto tmp:ed[i]) st.update(1, n, 1, mp[v[tmp]], 0);
    }
    cout<<ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if (pq.size()>=d)
      |             ~~~~~~~~~^~~
Main.cpp:46:18: warning: variable 'itr' set but not used [-Wunused-but-set-variable]
   46 |             auto itr=s.insert(make_pair(pq.top().first, -i));
      |                  ^~~

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