Submission #1115272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115272		sitablechair	Financial Report (JOI21_financial)	C++17	100 / 100	3605 ms	52376 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=3e5+3;

int n,d,a[N],dp[N];
vector<int> big,pos[N];
set<int> sus;

struct SegTree { 
    int tr[N*4];
    void build(int id,int l,int r,int val) {
        if (l==r) return void(tr[id]=val);
        int mid=l+r>>1;
        build(id*2,l,mid,val);
        build(id*2+1,mid+1,r,val);
        tr[id]=max(tr[id*2],tr[id*2+1]);
    }
    void update(int id,int l,int r,int u,int val) {
        if (l>u || r<u) return;
        int mid=l+r>>1;
        if (l==r) return void(tr[id]=val);
        update(id*2,l,mid,u,val);
        update(id*2+1,mid+1,r,u,val);
        tr[id]=max(tr[id*2],tr[id*2+1]);
    } 
    int query(int id,int l,int r,int u,int v) {
        if (l>v || r<u) return 0;
        if (l>=u && r<=v) return tr[id];
        int mid=l+r>>1;
        return max(query(id*2,l,mid,u,v),query(id*2+1,mid+1,r,u,v));
    }
} st,st1,st2;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d;
    For(i,1,n) {
        cin >> a[i];
        big.pb(a[i]);
    }   
    st.build(1,1,n,0);
    st1.build(1,1,n,0);
    st2.build(1,1,n,(int)(-2e9));
    sort(all(big));
    fill(dp,dp+1+n,1);
    For(i,1,n) {
        a[i]=(lower_bound(all(big),a[i])-big.begin())+1;
        pos[a[i]].pb(i);
    }
    For(i,1,n) {
        for(auto j: pos[i]) {
            if (i==1) continue;
            auto pp=sus.lower_bound(j);
            if (pp==sus.begin() || (j-(*prev(pp))>d)) continue;
            pp=prev(pp);
            int l=1,r=*pp;
            while(l<r) {
                int mid=l+(r-l)/2;
                auto hihi=sus.lower_bound(mid);
                if (hihi==pp) {
                    r=mid;
                    continue;
                }
                if (next(hihi)==pp) {
                    if (*pp-(*hihi)<=d) r=mid;
                    else l=mid+1;
                    continue;
                }
                int kk=max(st.query(1,1,n,(*hihi)+1,(*pp)-1),st1.query(1,1,n,(*hihi)+1,(*pp)-1));
                if (kk<=d) r=mid;
                else l=mid+1;
            }   
            dp[j]=max(dp[j],st2.query(1,1,n,r,*pp)+1);
        }
        for(auto j: pos[i]) {
            auto ptr=sus.insert(j).ff;
            st2.update(1,1,n,j,dp[j]);
            if (ptr!=sus.begin()) {
                st.update(1,1,n,j,j-(*prev(ptr)));
                st1.update(1,1,n,*prev(ptr),j-(*prev(ptr)));
            }
            if (next(ptr)!=sus.end()) {
                st1.update(1,1,n,j,(*next(ptr))-j);
                st.update(1,1,n,*next(ptr),(*next(ptr))-j);
            }
        }
    }
    int ans=-1;
    For(i,1,n) ans=max(ans,dp[i]);
    cout << ans;
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void SegTree::build(int, int, int, int)':
Main.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'void SegTree::update(int, int, int, int, int)':
Main.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'int SegTree::query(int, int, int, int, int)':
Main.cpp:56:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid=l+r>>1;
      |                 ~^~

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