oj.uz

Submission #854693

# Submission time Handle Problem Language Result Execution time Memory
854693 2023-09-28T14:20:24 Z kderylo Financial Report (JOI21_financial) C++17
0 / 100
 372 ms 43852 KB 
#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
const int stala=524288;
set<pair<int,int> >s; //war poz
vector<int>w[stala];
set<int>intervals;
int tab[stala];
int mapka[stala];
int range[stala];
int tree[2*stala];
int tree2[stala];
void remove_element(int index,int d)
{
    auto it=intervals.upper_bound(index);
    if(it==intervals.begin()){
        return;
    }
    it--;
    int pocz=*it;
    int kon=mapka[pocz];
    if(pocz<=index&&index<=kon){
        intervals.erase(it);
        int x1=pocz;
        int y1=index-1;
        int x2=index+1;
        int y2=kon;
        if(y1-x1+1>=d){
            intervals.insert(x1);
            mapka[x1]=y1;
        }
        if(y2-x2+1>=d){
            intervals.insert(x2);
            mapka[x2]=y2;
        }
    }
}
int find_range(int index,int ile,int d)
{
    auto it=intervals.upper_bound(index);
    if(it==intervals.end()){
        return ile;
    }
    return *it+d-1;
}
void update(int ind,int ind2,int war,int tr[])
{
    ind+=stala-1;
    ind2+=stala-1;
    tr[ind]=max(tr[ind],war);
    tr[ind2]=max(tr[ind2],war);
    while(ind/2!=ind2/2){
        if(ind%2==0){
            tr[ind+1]=max(tr[ind+1],war);
        }
        if(ind2%2==1){
            tr[ind2-1]=max(tr[ind2-1],war);
        }
        ind/=2;
        ind2/=2;
    }
}
int query(int ind,int tr[])
{
    ind+=stala-1;
    int wyn=0;
    while(ind>0){
        wyn=max(wyn,tr[ind]);
        ind/=2;
    }
    return wyn;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,d;
    cin>>ile>>d;
    for(int i=1;i<=ile;i++){
        int a;
        cin>>a;
        tab[i]=a;
        s.insert({a,i});
    }
    int pop=-1;
    int ind=0;
    while(!s.empty()){
        auto it=s.begin();
        int war=it->first;
        int poz=it->second;
        s.erase(it);
        if(war!=pop){
            pop=war;
            ind++;
        }
        w[ind].push_back(poz);
    }
    intervals.insert(1);
    mapka[1]=ile;
    for(int i=1;i<=ind;i++){
        for(int j=0;j<(int)w[i].size();j++){
            remove_element(w[i][j],d);
        }
        for(int j=0;j<(int)w[i].size();j++){
            range[w[i][j]]=find_range(w[i][j],ile,d);
        }
    }
    for(int i=1;i<=ind;i++){
        for(int j=0;j<(int)w[i].size();j++){
            int wyn=query(w[i][j],tree);
            tree2[w[i][j]]=wyn+1;
        }
        for(int j=0;j<(int)w[i].size();j++){
            int wyn=tree2[w[i][j]];
            update(w[i][j]+1,range[w[i][j]],wyn,tree);
        }
    }
    int res=tree2[ile];
    for(int i=1;i<=ile-1;i++){
        if(tab[i]>=tab[ile]&&range[i]==ile){
            res=max(res,tree2[i]);
        }
    }
    cout<<res;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 4 ms 20796 KB Output is correct
4 Correct 4 ms 20568 KB Output is correct
5 Correct 5 ms 20568 KB Output is correct
6 Incorrect 4 ms 20796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 4 ms 20796 KB Output is correct
4 Correct 4 ms 20568 KB Output is correct
5 Correct 5 ms 20568 KB Output is correct
6 Incorrect 4 ms 20796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 4 ms 20796 KB Output is correct
4 Correct 4 ms 20568 KB Output is correct
5 Correct 5 ms 20568 KB Output is correct
6 Incorrect 4 ms 20796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 40624 KB Output is correct
2 Correct 155 ms 41060 KB Output is correct
3 Correct 211 ms 41812 KB Output is correct
4 Correct 372 ms 40760 KB Output is correct
5 Correct 276 ms 40352 KB Output is correct
6 Correct 358 ms 43852 KB Output is correct
7 Correct 106 ms 38996 KB Output is correct
8 Incorrect 128 ms 40268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 40424 KB Output is correct
2 Correct 151 ms 41552 KB Output is correct
3 Correct 190 ms 41044 KB Output is correct
4 Correct 233 ms 40276 KB Output is correct
5 Correct 210 ms 40532 KB Output is correct
6 Correct 234 ms 40224 KB Output is correct
7 Correct 118 ms 40292 KB Output is correct
8 Incorrect 115 ms 40268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 4 ms 20572 KB Output is correct
3 Correct 4 ms 20796 KB Output is correct
4 Correct 4 ms 20568 KB Output is correct
5 Correct 5 ms 20568 KB Output is correct
6 Incorrect 4 ms 20796 KB Output isn't correct
7 Halted 0 ms 0 KB -