제출 #1172000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172000		imarn	Bouquet (EGOI24_bouquet)	C++20	100 / 100	121 ms	28560 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
#define sz(x) (ll)x.size()
#define cd complex<double>
using namespace std;
const int mxn=2e5+5;
int dpl[mxn]{0},dpr[mxn]{0},l[mxn],r[mxn];
vector<int>upl[mxn],upr[mxn];
struct seg{
    int t[2*mxn]{0};
    void upd(int i,int amt,int sz){
        i+=sz;t[i]=max(t[i],amt);
        for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
    }
    int qr(int l,int r,int sz,int rs=0){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)rs=max(rs,t[l++]);
            if(r&1)rs=max(rs,t[--r]);
        }return rs;
    }
}sg[2];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
    for(int i=1;i<=n;i++){
        for(auto it : upl[i])sg[0].upd(it,dpl[it],n+1);
        dpl[i]=sg[0].qr(1,i-l[i],n+1)+1;
        upl[min(i+r[i]+1,n+1)].pb(i);
    }
    for(int i=n;i>=1;i--){
        for(auto it : upr[i])sg[1].upd(it,dpr[it],n+1);
        dpr[i]=sg[1].qr(i+r[i]+1,n+1,n+1)+1;
        upr[max(0,i-l[i]-1)].pb(i);
    }int ans=0;for(int i=1;i<=n;i++)ans=max(ans,dpl[i]+dpr[i]-1);
    cout<<ans;
}

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