Submission #570944

#	Time	Username	Problem	Language	Result	Execution time	Memory
570944		dantoh000	Financial Report (JOI21_financial)	C++14	100 / 100	779 ms	52612 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
int n,d;
int a[300005];
int p[300005];
int l[300005];
int r[300005];
int ans[300005];
int ANS;
void init(int n){
    for (int i = 0; i < n; i++){
        p[i] = l[i] = r[i] = i;
    }
}
int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}
void un(int x, int y){
    x = find(x), y = find(y);
    if (x == y) return;
    p[y] = x;
    l[x] = min(l[x], l[y]);
    r[x] = max(r[x], r[y]);
}
struct node{
    int s,e,m,v;
    node *l, *r;
    node (int _s, int _e){
        s = _s, e = _e;
        m = (s+e)/2;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void up(int x, int nv){
        if (s == e){ v = nv; return;}
        if (x > m) r->up(x,nv);
        else l->up(x,nv);
        v = max(l->v,r->v);
    }
    int qu(int qs, int qe){
        ///printf("%d %d %d %d\n",s,e,qs,qe);
        if (qs ==s && qe ==e ) return v;
        if (qs > m) return r->qu(qs,qe);
        else if (qe <= m) return l->qu(qs,qe);
        else return max(l->qu(qs,m), r->qu(m+1,qe));
    }
} *root;
vector<ii> v;

bool cmp(ii a, ii b){
    if (a.fi != b.fi) return a.fi < b.fi;
    else return a.se > b.se;
}
int main(){
    scanf("%d%d",&n,&d);
    v.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d",&v[i].fi);
        v[i].se = i;
    }
    sort(v.begin(),v.end(),cmp);
    set<int> s;
    init(n);
    root = new node(0,n-1);
    for (int i = 0; i < n; i++){
        int ID = v[i].se;
        auto it = s.lower_bound(ID);
        if (it != s.end() && *it-ID <= d){
            un(*it, ID);
        }
        if (it != s.begin() && ID-*prev(it) <= d){
            un(*prev(it), ID);
        }
        s.insert(ID);
        int L = l[find(ID)];
        //printf("%d %d\n",ID,L);
        ans[ID] = root->qu(max(0,L-d), ID) + 1;
        //printf("ans %d\n",ans[ID]);
        root->up(ID, ans[ID]);
        ANS = max(ANS,ans[ID]);
    }
    printf("%d\n",ANS);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d%d",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d",&v[i].fi);
      |         ~~~~~^~~~~~~~~~~~~~~

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