Submission #564519

#	Time	Username	Problem	Language	Result	Execution time	Memory
564519		groshi	Financial Report (JOI21_financial)	C++17	100 / 100	284 ms	29668 KiB

Main

#include<iostream>
#include<utility>
#include<set>
#include<algorithm>
using namespace std;
multiset<int> secik;
set<pair<int,int>> wynik;
int t[2000000];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d;

    cin>>n>>d;
    for(int i=1;i<=n;i++)
        cin>>t[i];
    t[0]=1e9;
    for(int i=1;i<=n;i++)
    {
        secik.insert(t[i-1]);
        if(i-d-1>=0)
           secik.erase(secik.find(t[i-d-1]));
           //cout<<"ok\n";
        while(wynik.size() && *secik.begin()>(*wynik.begin()).first)
            wynik.erase(wynik.begin());
        auto it=wynik.lower_bound({t[i],0});
        //cout<<"ok2\n";
        if(it==wynik.end())
        {
            if(it==wynik.begin())
                wynik.insert({t[i],1});
            else{
                it--;
                wynik.insert({t[i],(*it).second+1});
            }
        }
        else if((*it).first!=t[i])
        {
            //cout<<"tako\n";
            if(it==wynik.begin())
            {
                if((*it).second==1)
                    wynik.erase(it);
                wynik.insert({t[i],1});
        }
        else{
            auto it2=it;
            it2--;
            int x=(*it2).second+1;
            if((*it).second==x)
                wynik.erase(it);
            wynik.insert({t[i],x});
        }
        //cout<<"koniec\n";
    }
    }
    //cout<<"zyje\n";
    auto it=wynik.rbegin();
    cout<<(*it).second;
    return 0;
}

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