Submission #705042

#	Time	Username	Problem	Language	Result	Execution time	Memory
705042		jakobrs	Mutating DNA (IOI21_dna)	C++17	35 / 100	48 ms	10288 KiB

dna

#include <iostream>
#include <vector>

struct Count {
  int a1, a2;
  int t1, t2;

  int at, ta;

  Count() : a1(0), a2(0), t1(0), t2(0), at(0), ta(0) {}

  Count operator+(const Count &rhs) const {
    Count res = *this;
    res += rhs;
    return res;
  }

  void operator+=(const Count &rhs) {
    a1 += rhs.a1;
    a2 += rhs.a2;
    t1 += rhs.t1;
    t2 += rhs.t2;
    at += rhs.at;
    ta += rhs.ta;
  }
};

struct SegmentTree {
  std::vector<Count> values;
  int offset;

  SegmentTree(int n) {
    offset = 1;
    while (offset < n) offset *= 2;

    values = std::vector<Count>(2 * offset);
  }

  void update(int idx, Count count_diff) {
    idx += offset;
    while (idx > 0) {
      values[idx] += count_diff;
      idx /= 2;
    }
  }

  Count query(int l, int r) const {
    Count count;

    l += offset;
    r += offset;
    while (l < r) {
      if (l & 1) count += values[l++];
      if (r & 1) count += values[--r];

      l /= 2;
      r /= 2;
    }

    return count;
  }
};

std::string a, b;
SegmentTree st(0);

void init(std::string A, std::string B) {
  a = A;
  b = B;

  st = SegmentTree(A.size());
  for (int i = 0; i < A.size(); i++) {
    Count diff;
    if (A[i] == 'A') diff.a1 += 1;
    if (B[i] == 'A') diff.a2 += 1;
    if (A[i] == 'T') diff.t1 += 1;
    if (B[i] == 'T') diff.t2 += 1;
    if (A[i] == 'A' && B[i] == 'T') diff.at += 1;
    if (A[i] == 'T' && B[i] == 'A') diff.ta += 1;
    st.update(i, diff);
  }
}

int get_distance(int x, int y) {
  y += 1;

  Count count = st.query(x, y);

  if (count.a1 != count.a2 || count.t1 != count.t2) {
    return -1;
  }

  return count.at;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int i = 0; i < A.size(); i++) {
      |                   ~~^~~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16