Submission #8872562

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////


struct Que{
    ll l,r;
    bool operator<(const Que a)const{
        return r<a.r;
    }
};
 

int main(){
    ll n;cin>>n;
    ll b[n];
    rep(i,0,n-1){
        cin>>b[i];
    }
    ll su[n];
    su[0]=0;
    rep(i,1,n){
        if(b[i-1]==1)su[i]=su[i-1];
        else su[i]=su[i-1]+1;
    }
    
    ll q;cin>>q;
    Que a[q];rep(i,0,q-1)cin>>a[i].l>>a[i].r;
    sort(a,a+q);
    ll dp[n+1];dp[0]=0;
    ll pos=0;
    //rep(i,0,n)cout<<su[i]<<" ";cout<<endl;
    rep(i,1,n){
        dp[i]=dp[i-1]+b[i-1];
        while(pos<=q-1&&a[pos].r==i){
            ll l=a[pos].l,r=a[pos].r;
            //cout<<dp[l-1]+(su[r]-su[l-1])<<endl;
            Min(dp[i],dp[l-1]+(su[r]-su[l-1]));
            pos++;
        }
    }
    //rep(i,0,n)cout<<dp[i]<<" ";cout<<endl;
    cout<<dp[n]<<endl;
    
    return 0;
}

Submission Info

Judge Result