제출 #331844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331844		quocnguyen1012	Colouring a rectangle (eJOI19_colouring)	C++14	100 / 100	1668 ms	44548 KiB

colouring

#include <bits/stdc++.h>


using namespace std;
using ll = long long;

const int maxn = 4e5 + 5;

struct segmenttree {
  vector<ll> st;
  vector<ll> lazy;
  int n;
  void init(int _n) {
    n = _n;
    st.assign(4 * n + 5, 0);
    lazy.assign(4 * n + 5, 0);
  }
#define lc id << 1
#define rc id << 1 | 1
  void push(int id, int l, int r) {
    st[id] += lazy[id];
    if (l != r) {
      lazy[lc] += lazy[id];
      lazy[rc] += lazy[id];
    }
    lazy[id] = 0;
  }
  void modify(int L, int R, ll v, int id, int l, int r) {
    push(id, l, r);
    if (R < l || r < L)
      return;
    if (L <= l && r <= R) {
      lazy[id] += v;
      push(id, l, r);
      return;
    }
    int mid = (l + r) / 2;
    modify(L, R, v, lc, l, mid);
    modify(L, R, v, rc, mid + 1, r);
    st[id] = min(st[lc], st[rc]);
  }
  void update(int pos, ll v, int id, int l, int r) {
    push(id, l, r);
    if (r < pos || pos < l)
      return;
    if (l == r) {
      st[id] = min(st[id], v);
      return;
    }
    int mid = (l + r) / 2;
    update(pos, v, lc, l, mid);
    update(pos, v, rc, mid + 1, r);
    st[id] = min(st[lc], st[rc]);
  }
  ll getmin(int L, int R, int id, int l, int r) {
    push(id, l, r);
    if (R < l || r < L)
      return 1e17;
    if (L <= l && r <= R)
      return st[id];
    int mid = (l + r) / 2;
    return min(getmin(L, R, lc, l, mid), getmin(L, R, rc, mid + 1, r));
  }
  void modify(int l, int r, ll v) {
    modify(l, r, v, 1, 0, n);
  }
  ll getmin(int l, int r) {
    return getmin(l, r, 1, 0, n);
  }
  void set(int pos, ll v) {
    update(pos, v, 1, 0, n);
  }
};

ll solve(vector<int> a, vector<int> b, vector<pair<int, int>> query) {
  int n = a.size(), m = b.size();
#ifdef LOCAL
  for (int i : a) cerr << i << ' '; cerr << '\n';
  for (int i : b) cerr << i << ' '; cerr << '\n';
  for (auto & it : query) cerr << it.first << ' ' << it.second << '\n';
#endif // LOCAL

  vector<int> order;
  for (int i = 1; i < n; ++i)
    order.push_back(i);
  sort(order.begin(), order.end(), [&](int x, int y) {
    return query[x - 1].first < query[y - 1].first;
  });

  vector<ll> sum(m + 5);
  for (int i = 1; i < m; ++i)
    sum[i] = sum[i - 1] + b[i];


  segmenttree st1;
  segmenttree st2;
  st1.init(m); st2.init(m);
  st1.modify(1, m, 1e15);
  st2.modify(1, m, 1e15);

  auto castdp = [&](int idx) {
    //cerr << idx << ' ';
    int l = query[idx - 1].first, r = query[idx - 1].second;

    ll v1 = st1.getmin(0, l - 1);
    ll v2 = st2.getmin(l, r);

    st1.modify(0, r, a[idx]);
    st2.modify(0, r, a[idx]);

    st1.set(r, v1 + sum[r] - sum[l - 1]);
    st2.set(r, v1 + sum[r] - sum[l - 1] - sum[r]);

    st1.set(r, v2 + sum[r]);
    st2.set(r, v2 + sum[r] - sum[r]);
  };

  for (int i : order) {
    castdp(i);
  }
  return st1.getmin(0, m);
}

int N, M;
int a[maxn], b[maxn];
int L[maxn], R[maxn];

signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL
  cin >> N >> M;
  int l = M , r = M;
  int v1 = 1, v2 = 1;
  for (int i = 1; i <= N + M - 1; ++i) {
    cin >> a[i];
    L[i] = l; R[i] = r;
    //cerr << l << ' ' << r << '\n';
    l -= v1; r += v2;
    if (l == 0) {
      l += 2;
      v1 = -v1;
    }
    if (r > N + M - 1) {
      r -= 2;
      v2 = -v2;
    }
  }
  for (int i = 1; i <= N + M - 1; ++i)
    cin >> b[i];

  ll res = 0;

  {
    vector<int> A, B;
    vector<pair<int, int>> query;
    bool ok = false;
    A.push_back(0); B.push_back(0);
    for (int i = 1; i <= N + M - 1; ++i) {
      if (i % 2 == 1) {
        A.push_back(a[i]);
        if (L[i] & 1) ok = true;
        query.push_back(make_pair((L[i] + 1) / 2, (R[i] + 1) / 2));
      }
    }
    for (int i = 1; i <= N + M - 1; ++i) {
      if (ok) {
        if (i % 2 == 1) {
          B.push_back(b[i]);
        }
      } else {
        if (i % 2 == 0) {
          B.push_back(b[i]);
        }
      }
    }
    res += solve(A, B, query);
  }
  {
    vector<int> A, B;
    vector<pair<int, int>> query;
    bool ok = false;
    A.push_back(0); B.push_back(0);
    for (int i = 1; i <= N + M - 1; ++i) {
      if (i % 2 == 0) {
        A.push_back(a[i]);
        if (L[i] & 1) ok = true;
        query.push_back(make_pair((L[i] + 1) / 2, (R[i] + 1) / 2));
      }
    }
    for (int i = 1; i <= N + M - 1; ++i) {
      if (ok) {
        if (i % 2 == 1) {
          B.push_back(b[i]);
        }
      } else {
        if (i % 2 == 0) {
          B.push_back(b[i]);
        }
      }
    }
    res += solve(A, B, query);
  }

  cout << res;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20