Submission #3996554

---

Source Code Expand

#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;
const LL INF = 0x3fffffffff;

int N;
int Q;
int bs[214514];
int dp[214514];

struct LazySeg {
  int size;
  vector<char> has_lazy;
  vector<LL> seg;
  vector<LL> lazy;
  vector<LL> width;
  vector<LL> assi;

  LazySeg(vector<LL> A) {
    int n = A.size();
    size = 1;
    while (size < n) size *= 2;

    seg.resize(size);
    seg.insert(seg.end(), A.begin(), A.end());
    seg.resize(size*2);
    lazy.resize(size*2);
    has_lazy.resize(size*2);
    width.resize(size*2);
    assi.resize(size*2);
    rrep(i, size) {
      seg[i] = min(seg[i*2], seg[i*2+1]);
      width[i] = width[i*2] + width[i*2+1]; 
    }
  }

  void LazyPropagate(int k) {
    if (has_lazy[k]) {
      seg[k] = assi[k];
      if (k < size) {
        has_lazy[k*2] = true;
        has_lazy[k*2+1] = true;
        assi[k*2] = assi[k]; 
        assi[k*2+1] = assi[k];
        lazy[k*2] = 0;
        lazy[k*2+1] = 0;
      }
      has_lazy[k] = false;
    }

    seg[k] += lazy[k];
    if (k < size) {
      lazy[k*2] += lazy[k];
      lazy[k*2+1] += lazy[k];
    }
    lazy[k] = 0;
  }

  void Add(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      lazy[k] += x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Add(wishl, wishr, k*2, watchl, mid, x);
    Add(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = min(seg[k*2], seg[k*2+1]);
  }

  void Move(int wishl, int wishr, int k, int watchl, int watchr, LL x) {
    if (wishr <= watchl || watchr <= wishl) {
      LazyPropagate(k);
      return;
    }

    if (wishl <= watchl && watchr <= wishr) {
      has_lazy[k] = true;
      lazy[k] = 0;
      assi[k] = x;
      LazyPropagate(k);
      return;
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    Move(wishl, wishr, k*2, watchl, mid, x);
    Move(wishl, wishr, k*2+1, mid, watchr, x);
    seg[k] = min(seg[k*2], seg[k*2+1]);
  }

  void Add(int wishl, int wishr, LL x) {
    return Add(wishl, wishr, 1, 0, size, x);
  }

  void Move(int wishl, int wishr, LL x) {
    return Move(wishl, wishr, 1, 0, size, x);
  }

  LL Get(int wishl, int wishr, int k, int watchl, int watchr) {
    LL lval, rval;

    if (wishr <= watchl || watchr <= wishl) return INF;

    if (wishl <= watchl && watchr <= wishr) {
      LazyPropagate(k);
      return seg[k];
    }

    LazyPropagate(k);
    int mid = (watchl+watchr)/2;
    lval = Get(wishl, wishr, k*2, watchl, mid);
    rval = Get(wishl, wishr, k*2+1, mid, watchr);
    return min(lval, rval);
  }

  LL Get(int wishl, int wishr) {
    return Get(wishl, wishr, 1, 0, size);
  }
};

int main() {
  scanf("%d", &N);
  reps(i, 1, N+1) {
    scanf("%d", &bs[i]);
  }

  scanf("%d", &Q);

  vector<pii> segs;
  rep(i, Q) {
    int l, r;
    scanf("%d%d", &l, &r);
    ++r;
    segs.eb(pii(l, r));
  }
  sort(all(segs), greater<pii>());

  // dp[i][j] := we've processed [1, i).  should fill with 1s [*, j)
  LazySeg seg(vector<LL>(N+10, INF/2));
  seg.Move(0, 1, 0);
  reps(i, 1, N+1) {
    // dp[i+1][k] <- dp[i][*]
    //cout << "i: " << i << endl;
    while (1) {
      auto s = segs.back();
      if (s.X != i) break;
      segs.pop_back();

      //cout << "process " << s.X << ", " << s.Y << endl;
      int r = s.Y;
      LL v = seg.Get(0, r+1);
      seg.Move(r, r+1, v);
    }

    /*cout << "seg: ";
    rep(j, N+2) {
      auto v = seg.Get(j, j+1);
      if (v < INF/2) cout << v << " ";
      else cout << "INF" << " ";
    }cout << endl;*/

    LL x = seg.Get(0, 1);
    LL y = seg.Get(i+1, i+2);
    seg.Move(0, 1, min(x+bs[i], y+!bs[i]));
    if (!bs[i]) {
      seg.Add(i+2, N+3, 1);
    }
    seg.Move(i+1, i+2, INF/2);

    /*cout << "seg: ";
    rep(j, N+2) {
      auto v = seg.Get(j, j+1);
      if (v < INF/2) cout << v << " ";
      else cout << "INF" << " ";
    }cout << endl;*/
  }
  assert(segs.empty());
  printf("%lld\n", seg.Get(0, N+3));
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:153:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:155:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &bs[i]);
                        ^
./Main.cpp:158:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Q);
                  ^
./Main.cpp:163:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &l, &r);
                          ^

Judge Result