Submission #479397

#	Time	Username	Problem	Language	Result	Execution time	Memory
479397		nicolaalexandra	Financial Report (JOI21_financial)	C++14	100 / 100	670 ms	23380 KiB

Main

#include <bits/stdc++.h>
#define DIM 300010
using namespace std;

pair <int,int> v[DIM];
set <int> s;
int t[DIM],poz_min[DIM],aint[DIM*4];
int n,d,i,j;

inline int cmp (pair<int,int> a, pair<int,int> b){
    if (a.first == b.first)
        return a.second > b.second;
    return a.first < b.first;
}

inline int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}


void uneste (int x, int y){

    int radx = get_rad(x), rady = get_rad(y);
    if (radx == rady)
        return;

    if (t[radx] > t[rady])
        swap (radx,rady);

    t[radx] += t[rady];
    t[rady] = radx;

    poz_min[radx] = min (poz_min[radx],poz_min[rady]);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

int query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y)
        return aint[nod];

    int mid = (st+dr)>>1, sol_st = 0, sol_dr = 0;
    if (x <= mid)
        sol_st = query (nod<<1,st,mid,x,y);
    if (y > mid)
        sol_dr = query ((nod<<1)|1,mid+1,dr,x,y);
    return max (sol_st,sol_dr);
}

inline int modul (int n){
    return max (n,-n);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>d;
    for (i=1;i<=n;i++){
        cin>>v[i].first;
        v[i].second = i;

        t[i] = -1;
        poz_min[i] = i;
    }

    sort (v+1,v+n+1,cmp);

    for (i=1;i<=n;i++){

        /// fac padurile
        int poz = v[i].second;
        set <int> :: iterator it = s.lower_bound (poz);
        if (it != s.end()){
            if (modul(*it - poz) <= d)
                uneste (*it,poz);
        }
        if (it != s.begin()){
            it--;
            if (modul(*it - poz) <= d)
                uneste (*it,poz);
        }

        s.insert(poz);


        int poz2 = poz_min[get_rad(poz)];

        int val = 1;
        if (poz2 < poz)
            val = max(val, query (1,1,n,poz2,poz) + 1);

        update (1,1,n,poz,val);
    }

    cout<<aint[1];

    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