Submission #953231

#	Time	Username	Problem	Language	Result	Execution time	Memory
953231		happy_node	Financial Report (JOI21_financial)	C++17	100 / 100	399 ms	39104 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MX=3e5+5;
 
int dp[MX], R[MX];
 
struct segtree {
        pair<int,int> t[4*MX];
 
        void update(int v, int l, int r, int pos, pair<int,int> val) {
                if(l>pos||r<pos) return;
                if(l==r) {
                        t[v]=val;
                        return;
                }
                int mid=(l+r)>>1;
                update(v*2+0,l,mid+0,pos,val);
                update(v*2+1,mid+1,r,pos,val);
                t[v]=max(t[v*2+0],t[v*2+1]);
        }
 
        pair<int,int> query(int v, int l, int r, int ql, int qr) {
                if(qr<l||r<ql) return make_pair(-1,-1);
                if(ql<=l&&qr>=r) return t[v];
                int mid=(l+r)>>1;
                return max(query(v*2+0,l,mid+0,ql,qr),
                        query(v*2+1,mid+1,r,ql,qr));
        }
 
        void reset() {
                for(int i=0;i<4*MX;i++) {
                        t[i]=make_pair(-1,-1);
                }
        }
} st;
 
int rev[MX];

struct DSU {
        int par[MX];

        int find(int v) {
                return par[v]==v?v:par[v]=find(par[v]);
        }

        bool merge(int u, int v) { // v itu yang lebih gede
                u=find(u),v=find(v);
                if(u==v) return 0;
                par[u]=v;
                return 1;
        }

        void prep() {
                for(int i=0;i<MX;i++) par[i]=i;
        }
} ds;
 
int solveChallange(int N, int D, std::vector<int> H) { 
        st.reset();
 
        vector<pair<int,int>> ord;
        vector<int> P(N);
 
        for(int i=0;i<N;i++) {
                ord.push_back({H[i],-i});
        }
        sort(ord.begin(),ord.end());
        int cnt=1;
        for(auto [h,id]:ord) {
                id=-id;
                P[id]=cnt++;
                rev[P[id]]=id; // dapetin posisi dia
        }

        ds.prep();

        set<int> pt;
        for(int i=1;i<=N;i++) {
                int p=rev[i];
                auto it=pt.lower_bound(p);
                if(it!=pt.end()&&(*it)-p<=D) ds.merge(p,*it);
                if(it!=pt.begin()) {
                        it--;
                        if(p-(*it)<=D)
                                ds.merge(*it,p);
                }
                pt.insert(p);
                R[p]=min(N-1,ds.find(p)+D);
        }

        for(int i=0;i<N;i++) {
                while(true) {
                        auto [V,p]=st.query(1,1,N,1,P[i]-1);
                        if(p==-1) break;
                        if(R[p]<i) {
                                st.update(1,1,N,P[p],make_pair(-1,-1));
                                continue;
                        }
                        dp[i]=V+1;
                        break;
                }
 
                dp[i]=max(dp[i],1);
                st.update(1,1,N,P[i],make_pair(dp[i],i));
        }
 
        return *max_element(dp,dp+N);
}
 
 
int main() {
        int N, D;
        std::vector<int> H;
        scanf("%d %d", &N, &D);
        H.resize(N);
        for (auto &elem : H) {
        scanf("%d", &elem);
        }
        int answer = solveChallange(N, D, H);
        printf("%d\n", answer);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         scanf("%d %d", &N, &D);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf("%d", &elem);
      |         ~~~~~^~~~~~~~~~~~~

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