Submission #1088186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088186		Almonther	Bouquet (EGOI24_bouquet)	C++98	100 / 100	91 ms	13168 KiB

Main

#include <bits/stdc++.h>

#define suiii ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define co cout<<
//#pragma GCC optimize("O3,Ofast,unroll-loops")
//#pragma GCC target("avx2,sse3,sse4,avx")
using namespace std;
//stuff
const ll N=exp2(ceil(log2(2e5)));
ll tre[N*4],n,dp[1000001],l[1000001],r[1000001];
ll mxof(ll l,ll r,ll i,ll lq,ll rq){
    if(l>rq||r<lq) return 0;
    if(l>=lq&&r<=rq) return tre[i];
    ll mid=(l+r)/2;
    return max(mxof(l,mid,i*2,lq,rq),mxof(mid+1,r,i*2+1,lq,rq));
}
void solve(){
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>l[i]>>r[i];
        l[i]=min(i,l[i]);
        r[i]=min(n-i-1,r[i]);
    }
    ll mx=0;
    priority_queue<pair<ll,ll>>q;
    for(int i=0;i<n;i++){
        while(q.size()&&-q.top().first<=i){
            ll idx=q.top().second+N;
            q.pop();
            tre[idx]=dp[idx-N];
            idx/=2;
            while(idx){
                tre[idx]=max(tre[idx*2],tre[idx*2+1]);
                idx/=2;
            }
        }
        if(i-l[i]-1<0){
            dp[i]=1;
            mx=max(mx,dp[i]);
            q.push({-(i+r[i]+1),i});
            continue;
        }
        dp[i]=mxof(0,N-1,1,0,i-l[i]-1)+1;
        mx=max(mx,dp[i]);
        q.push({-(i+r[i]+1),i});
    }
    co mx;
}
int main()
{
    suiii
    int _=1;
    // cin>>_;
    while(_--) solve();
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30