Submission #332051

#	Time	Username	Problem	Language	Result	Execution time	Memory
332051		LifeHappen__	Colouring a rectangle (eJOI19_colouring)	C++14	100 / 100	1105 ms	84204 KiB

colouring

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ar array

const int N = 4e5 + 5;
struct trie {
  int it[N << 2];
  int lz[N << 2];
  trie() {
    memset(it, 0x3f, sizeof it);
    memset(lz, 0, sizeof lz);
  }
  void dolazy(int i) {
    if(lz[i]) {
      int val = lz[i];
      lz[i << 1] += val;
      lz[i << 1 | 1] += val;
      it[i << 1] += val;
      it[i << 1 | 1] += val;
      lz[i] = 0;
    }
  }
  void update(int i, int l, int r, int u, int v, int val) {
    if(v < l || u > r) return;
    if(u <= l && r <= v) {
      it[i] += val;
      lz[i] += val;
      return;
    }
    int mid = l + (r - l) / 2;
    dolazy(i);
    update(i << 1, l, mid, u, v, val);
    update(i << 1 | 1, mid + 1, r, u, v, val);
    it[i] = min(it[i << 1], it[i << 1 | 1]);
  }
  void update(int i, int l, int r, int pos, int val) {
    if(pos < l || pos > r) return;
    if(l == r) {
      it[i] = val;
      return;
    }
    int mid = l + (r - l) / 2;
    dolazy(i);
    update(i << 1, l, mid, pos, val);
    update(i << 1 | 1, mid + 1, r, pos, val);
    it[i] = min(it[i << 1], it[i << 1 | 1]);
  }
  int query(int i, int l, int r, int u, int v) {
    if(v < l || u > r) return 1e15;
    if(u <= l && r <= v) return it[i];
    int mid = l + (r - l) / 2;
    dolazy(i);
    return min(query(i << 1, l, mid, u, v), query(i << 1 | 1, mid + 1, r, u, v));
  }
} p1, p2;
int n, m, a[N];
ii b[N];
int s[N], pos[N], le[N], ri[N], p[N];

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  cin >> n >> m;
  for (int i = 1; i <= n + m - 1; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n + m - 1; ++i) {
    cin >> b[i].se;
    b[i].fi = i;
  }
  int nn = n + m - 1;
  sort(b + 1, b + nn + 1, [](ii x, ii y) {
    int u = x.fi % 2;
    int v = y.fi % 2;
    if(u != v) return u == 1;
    else return x.fi < y.fi;
  });

  s[0] = 0;
  for (int i = 1; i <= nn; ++i) {
    pos[b[i].fi] = i;
    s[i] = s[i - 1] + b[i].se;
  }
  int x = m, y = m, dx = -1, dy = 1;
  for (int i = 1; i <= nn; ++i) {
    le[i] = pos[x];
    ri[i] = pos[y];
    if(x == 1) dx = 1;
    if(y == m + n - 1) dy = -1;
    x += dx;
    y += dy;
    p[i] = i;
  }
  sort(p + 1, p + nn + 1, [](int x, int y) {
    return le[x] < le[y];
  });
  p1.update(1, 0, nn, 0, 0);
  p2.update(1, 0, nn, 0, 0);
  n = nn;
  for (int j = 1; j <= nn; ++j) {
    int i = p[j];
    int fir;
    fir = p1.query(1, 0, nn, 0, le[i] - 1) + s[ri[i]] - s[le[i] - 1];
    fir = min(fir, p2.query(1, 0, nn, le[i], ri[i]) + s[ri[i]]);
    p1.update(1, 0, nn, ri[i], ri[i], a[i]);
    fir = min(p1.query(1, 0, nn, ri[i], ri[i]), fir);
    p1.update(1, 0, nn, ri[i], fir);
    p2.update(1, 0, nn, ri[i], fir - s[ri[i]]);
    p1.update(1, 0, nn, 0, ri[i] - 1, a[i]);
    p2.update(1, 0, nn, 0, ri[i] - 1, a[i]);
  }
  cout << p1.it[1] << '\n';
}

• 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