Submission #5558744

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

struct SegmentTree{
    const int INF = 1e9;
    int n, width;
    VI dat;

    void init(int x){
        n = x;
        width = 1;
        while (width < n) width *= 2;
        dat.resize(2*width-1);
        REP(i,2*width-1) dat[i] = INF;
    }

    void update(int i, int x){
        i += width - 1;
        dat[i] = x;
        while (i > 0){
            i = (i - 1) / 2;
            dat[i] = min(dat[i*2+1], dat[i*2+2]);
        }
    }

    int query(int a, int b, int k, int l, int r){
        if (r <= a || b <= l) return INF;
        if (a <= l && r <= b) return dat[k];
        int vl = query(a, b, k*2+1, l, (l+r)/2);
        int vr = query(a, b, k*2+2, (l+r)/2, r);
        return min(vl, vr);
    }

    // [l, r)
    int query(int l, int r){
        return query(l, r, 0, 0, width);
    }
};

int main() {
    int n;
    cin >> n;
    VI a(n), s0(n + 1), s1(n + 1);
    REP(i,n){
        a[i] = in();
        s0[i + 1] = s0[i] + (a[i] == 0);
        s1[i + 1] = s1[i] + (a[i] == 1);
    }
    int q;
    cin >> q;
    VVI r(n);
    REP(i,q){
        int x = in() - 1, y = in();
        r[x].push_back(y);
    }

    SegmentTree seg0, seg1;
    seg0.init(n + 1);
    seg1.init(n + 1);
    seg0.update(0, 0);
    seg1.update(0, 0);

    REP(i,n){
        for (int x : r[i]){
            int d = min(
                seg0.query(0, i) + s1[i] + s0[x] - s0[i],
                seg1.query(i, x) + s0[x]
            );
            seg0.update(x, d - s1[x]);
            seg1.update(x, d - s0[x]);
        }
    }

    int ans = seg0.query(0, n + 1) + s1[n];
    cout << ans << endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:36:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘ll lin()’:
./Main.cpp:37:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll lin() { ll x; scanf("%lld", &x); return x; }
                                   ^

Judge Result