Submission #5558763


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;
        chmin(dat[i], x);
        // 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

Submission Time
Task F - NRE
User TangentDay
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2650 Byte
Status AC
Exec Time 195 ms
Memory 15360 KB

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

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 7
AC × 127
Set Name Test Cases
Sample example_0, example_1, example_2, example_3, example_4, example_5, example_6
All cent_0, cent_1, cent_2, cent_3, cent_4, cent_5, cent_6, cent_7, cent_8, cent_9, example_0, example_1, example_2, example_3, example_4, example_5, example_6, full_0, full_1, full_10, full_11, full_12, full_13, full_14, full_15, full_16, full_17, full_18, full_19, full_2, full_3, full_4, full_5, full_6, full_7, full_8, full_9, maxrand_0, maxrand_1, maxrand_10, maxrand_11, maxrand_12, maxrand_13, maxrand_14, maxrand_15, maxrand_16, maxrand_17, maxrand_18, maxrand_19, maxrand_2, maxrand_20, maxrand_21, maxrand_22, maxrand_23, maxrand_24, maxrand_25, maxrand_26, maxrand_27, maxrand_28, maxrand_29, maxrand_3, maxrand_4, maxrand_5, maxrand_6, maxrand_7, maxrand_8, maxrand_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_2, small_3, small_4, small_5, small_6, small_7, small_8, small_9, smallwidth_0, smallwidth_1, smallwidth_10, smallwidth_11, smallwidth_12, smallwidth_13, smallwidth_14, smallwidth_15, smallwidth_16, smallwidth_17, smallwidth_18, smallwidth_19, smallwidth_2, smallwidth_20, smallwidth_21, smallwidth_22, smallwidth_23, smallwidth_24, smallwidth_25, smallwidth_26, smallwidth_27, smallwidth_28, smallwidth_29, smallwidth_3, smallwidth_4, smallwidth_5, smallwidth_6, smallwidth_7, smallwidth_8, smallwidth_9
Case Name Status Exec Time Memory
cent_0 AC 171 ms 14072 KB
cent_1 AC 189 ms 14848 KB
cent_2 AC 162 ms 13428 KB
cent_3 AC 172 ms 14332 KB
cent_4 AC 170 ms 14456 KB
cent_5 AC 163 ms 13556 KB
cent_6 AC 170 ms 14328 KB
cent_7 AC 165 ms 13944 KB
cent_8 AC 176 ms 14976 KB
cent_9 AC 164 ms 13556 KB
example_0 AC 1 ms 256 KB
example_1 AC 1 ms 256 KB
example_2 AC 1 ms 256 KB
example_3 AC 1 ms 256 KB
example_4 AC 1 ms 256 KB
example_5 AC 1 ms 256 KB
example_6 AC 1 ms 256 KB
full_0 AC 23 ms 11392 KB
full_1 AC 173 ms 15232 KB
full_10 AC 24 ms 11392 KB
full_11 AC 173 ms 15232 KB
full_12 AC 24 ms 11392 KB
full_13 AC 172 ms 15232 KB
full_14 AC 23 ms 11392 KB
full_15 AC 173 ms 15232 KB
full_16 AC 23 ms 11392 KB
full_17 AC 176 ms 15232 KB
full_18 AC 23 ms 11392 KB
full_19 AC 177 ms 15232 KB
full_2 AC 24 ms 11392 KB
full_3 AC 176 ms 15232 KB
full_4 AC 24 ms 11392 KB
full_5 AC 180 ms 15232 KB
full_6 AC 23 ms 11392 KB
full_7 AC 182 ms 15232 KB
full_8 AC 23 ms 11392 KB
full_9 AC 175 ms 15232 KB
maxrand_0 AC 24 ms 11392 KB
maxrand_1 AC 181 ms 14976 KB
maxrand_10 AC 24 ms 11392 KB
maxrand_11 AC 181 ms 14976 KB
maxrand_12 AC 24 ms 11392 KB
maxrand_13 AC 183 ms 14976 KB
maxrand_14 AC 24 ms 11392 KB
maxrand_15 AC 180 ms 14976 KB
maxrand_16 AC 23 ms 11392 KB
maxrand_17 AC 179 ms 14976 KB
maxrand_18 AC 25 ms 11392 KB
maxrand_19 AC 182 ms 14976 KB
maxrand_2 AC 23 ms 11392 KB
maxrand_20 AC 24 ms 11392 KB
maxrand_21 AC 195 ms 14976 KB
maxrand_22 AC 25 ms 11392 KB
maxrand_23 AC 187 ms 14976 KB
maxrand_24 AC 24 ms 11392 KB
maxrand_25 AC 178 ms 14976 KB
maxrand_26 AC 23 ms 11392 KB
maxrand_27 AC 180 ms 14976 KB
maxrand_28 AC 23 ms 11392 KB
maxrand_29 AC 185 ms 14976 KB
maxrand_3 AC 183 ms 14976 KB
maxrand_4 AC 23 ms 11392 KB
maxrand_5 AC 186 ms 14976 KB
maxrand_6 AC 24 ms 11392 KB
maxrand_7 AC 187 ms 14976 KB
maxrand_8 AC 25 ms 11392 KB
maxrand_9 AC 184 ms 14976 KB
rand_0 AC 187 ms 14976 KB
rand_1 AC 95 ms 4864 KB
rand_10 AC 181 ms 14976 KB
rand_11 AC 63 ms 7936 KB
rand_12 AC 185 ms 14976 KB
rand_13 AC 130 ms 11520 KB
rand_14 AC 183 ms 14976 KB
rand_15 AC 76 ms 3840 KB
rand_16 AC 181 ms 14976 KB
rand_17 AC 98 ms 7296 KB
rand_18 AC 181 ms 14976 KB
rand_19 AC 155 ms 13824 KB
rand_2 AC 181 ms 14976 KB
rand_3 AC 132 ms 4992 KB
rand_4 AC 180 ms 14976 KB
rand_5 AC 78 ms 1792 KB
rand_6 AC 188 ms 14976 KB
rand_7 AC 107 ms 6784 KB
rand_8 AC 178 ms 14976 KB
rand_9 AC 36 ms 10240 KB
small_0 AC 1 ms 256 KB
small_1 AC 1 ms 256 KB
small_2 AC 1 ms 256 KB
small_3 AC 1 ms 256 KB
small_4 AC 1 ms 256 KB
small_5 AC 1 ms 256 KB
small_6 AC 1 ms 256 KB
small_7 AC 1 ms 256 KB
small_8 AC 1 ms 256 KB
small_9 AC 1 ms 256 KB
smallwidth_0 AC 23 ms 11392 KB
smallwidth_1 AC 163 ms 15360 KB
smallwidth_10 AC 22 ms 11392 KB
smallwidth_11 AC 142 ms 15360 KB
smallwidth_12 AC 23 ms 11392 KB
smallwidth_13 AC 164 ms 15360 KB
smallwidth_14 AC 22 ms 11392 KB
smallwidth_15 AC 143 ms 15360 KB
smallwidth_16 AC 23 ms 11392 KB
smallwidth_17 AC 165 ms 15360 KB
smallwidth_18 AC 23 ms 11392 KB
smallwidth_19 AC 149 ms 15360 KB
smallwidth_2 AC 24 ms 11392 KB
smallwidth_20 AC 24 ms 11392 KB
smallwidth_21 AC 163 ms 15360 KB
smallwidth_22 AC 23 ms 11392 KB
smallwidth_23 AC 144 ms 15360 KB
smallwidth_24 AC 24 ms 11392 KB
smallwidth_25 AC 166 ms 15360 KB
smallwidth_26 AC 23 ms 11392 KB
smallwidth_27 AC 143 ms 15360 KB
smallwidth_28 AC 23 ms 11392 KB
smallwidth_29 AC 163 ms 15360 KB
smallwidth_3 AC 143 ms 15360 KB
smallwidth_4 AC 23 ms 11392 KB
smallwidth_5 AC 163 ms 15360 KB
smallwidth_6 AC 23 ms 11392 KB
smallwidth_7 AC 143 ms 15360 KB
smallwidth_8 AC 23 ms 11392 KB
smallwidth_9 AC 163 ms 15360 KB