Submission #1030040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030040		TraianDanciu	Colouring a rectangle (eJOI19_colouring)	C++17	100 / 100	505 ms	37236 KiB

colouring

#include <stdio.h>
#include <vector>

static inline long long min(long long a, long long b) {
  return a < b ? a : b;
}
static inline long long max(long long a, long long b) {
  return a > b ? a : b;
}

#define MAXN 200000
#define INFINIT 1000000000000000000

int a[MAXN * 2];
struct Restrictie {
  int st, dr, val;
} v[MAXN * 2];

int cost[MAXN], st[MAXN], p[MAXN];
std::vector<int> dr[MAXN];

struct SegmentTree {
  long long aint[4 * (MAXN + 1)], lazy[4 * (MAXN + 1)], qval;
  int n, qleft, qright;

  void init(int n) {
    int i;
    
    this->n = n;
    for(i = 0; i < 4 * n; i++) {
      aint[i] = lazy[i] = 0;
    }
  }

  void propagate(int node, int left, int right) {
    aint[node] += lazy[node];
    if(left < right) {
      lazy[2 * node + 1] += lazy[node];
      lazy[2 * node + 2] += lazy[node];
    }
    lazy[node] = 0;
  }

  void _update(int node, int left, int right) {
    int middle;

    propagate(node, left, right);
    if(qleft <= left && right <= qright) {
      lazy[node] += qval;
      propagate(node, left, right);
    } else {
      middle = (left + right) / 2;
      propagate(2 * node + 1, left, middle);
      propagate(2 * node + 2, middle + 1, right);
      if(qleft <= middle) {
        _update(2 * node + 1, left, middle);
      }
      if(middle < qright) {
        _update(2 * node + 2, middle + 1, right);
      }
      aint[node] = min(aint[2 * node + 1], aint[2 * node + 2]);
    }
  }
  void update(int qleft, int qright, long long qval) {
    this->qleft = qleft;
    this->qright = qright;
    this->qval = qval;
    _update(0, 0, n - 1);
  }

  long long _query(int node, int left, int right) {
    int middle;
    long long ans;

    propagate(node, left, right);
    if(qleft <= left && right <= qright) {
      return aint[node];
    }

    middle = (left + right) / 2;
    ans = INFINIT;
    if(qleft <= middle) {
      ans = min(ans, _query(2 * node + 1, left, middle));
    }
    if(middle < qright) {
      ans = min(ans, _query(2 * node + 2, middle + 1, right));
    }

    return ans;
  }
  long long query(int qleft, int qright) {
    this->qleft = qleft;
    this->qright = qright;
    return _query(0, 0, n - 1);
  }
} aint;

int main() {
  int n, m, i, j, l, c, j1, j2, nnou;
  long long ans;

  scanf("%d%d", &n, &m);
  for(i = 0; i < n + m - 1; i++) {
    scanf("%d", &a[i]);
  }
  for(i = 0; i < n + m - 1; i++) {
    scanf("%d", &v[i].val);

    c = min(i, m - 1);
    l = i - c;
    v[i].st = l - c + m - 1;
    
    c = max(0, i - n + 1);
    l = i - c;
    v[i].dr = l - c + m - 1;
  }

  ans = 0;
  for(j1 = 0; j1 < 2; j1++) {
    j2 = v[j1].st % 2;

    nnou = 0;
    for(i = j1; i < n + m - 1; i += 2) {
      cost[nnou++] = a[i];
    }
    for(i = j2; i < n + m - 1; i += 2) {
      st[i / 2] = v[i].st / 2;
      dr[v[i].dr / 2].push_back(i / 2);
      p[i / 2] = v[i].val;
    }

    aint.init(nnou + 1);
    for(i = 0; i < nnou; i++) {
      aint.update(i + 1, i + 1, aint.query(0, i));
      aint.update(0, i, cost[i]);
      for(j = 0; j < (int)dr[i].size(); j++) {
        aint.update(st[dr[i][j]] + 1, i + 1, p[dr[i][j]]);
      }
    }
    ans += aint.query(0, nnou);

    for(i = 0; i < nnou; i++) {
      dr[i].clear();
    } 
  }

  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

colouring.cpp: In function 'int main()':
colouring.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
colouring.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
colouring.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d", &v[i].val);
      |     ~~~~~^~~~~~~~~~~~~~~~~

• 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