Submission #3995752

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)







class SegmentTree
{
private:
    ll n;    // 配列の要素数
    ll s;    // 配列を初期化するときの値
    vector<ll> data;     // セグメントツリーを持つ配列
public:
    SegmentTree(ll m, ll t);   // mは配列の要素数、tは配列を初期化するときの値
    ll operation(ll t1, ll t2); // 二項演算
    void update(ll k, ll a);  // k番目(0-indexed)の値をaに変更
    ll query(ll a, ll b);   // [a, b) の値を求める。
    ll query(ll a, ll b, ll k, ll l, ll r);   // [a, b) の値を求める。
};

SegmentTree::SegmentTree(ll m, ll t){
    n = 1;
    
    while(n < m) n *= 2;
    
    data.assign(2 * n - 1, t);
    
    s = t;
}

ll SegmentTree::operation(ll t1, ll t2){
    return min(t1, t2);
}

void SegmentTree::update(ll k, ll a){
    k += n - 1;
    data[k] = a;
    
    while(k > 0){
        k = (k - 1) / 2;
        data[k] = operation(data[k * 2 + 1], data[k * 2 + 2]);
    }
}

ll SegmentTree::query(ll a, ll b){
    return query(a, b, 0, 0, n);
}

ll SegmentTree::query(ll a, ll b, ll k, ll l, ll r){
    if(r <= a || b <= l) return s;
    if(a <= l && r <= b){
        return data[k];
    }
    else{
        ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        
        return operation(vl, vr);
    }
}

int main() {
    ll n;
    cin >> n;
    ll cnt = 0;
    vector<ll> b(n + 1);
    REP(i, n){
        cin >> b[i + 1];
        if(b[i + 1] == 0) cnt++;
    }
    ll q;
    cin >> q;
    vector<vector<ll>> v(n + 1);
    REP(i, q){
        ll l, r;
        cin >> l >> r;
        v[l].push_back(r);
    }
    
    SegmentTree st(n + 1, INF);
    st.update(0, 0);
    for(ll i = 1; i <= n; i++){
        sort(v[i].rbegin(), v[i].rend());
        for(auto &r : v[i]){
            ll res = st.query(i - 1, r);
            if(res < st.query(r, r + 1)) st.update(r, res);
        }
        ll res = st.query(i - 1, i) + (b[i]? 1 : -1);
        if(res < st.query(i, i + 1)) st.update(i, res);
    }
    cout << st.query(n, n + 1) + cnt << endl;
}

Submission Info

Judge Result