Submission #580216

#	Time	Username	Problem	Language	Result	Execution time	Memory
580216		adrilen	Mutating DNA (IOI21_dna)	C++17	100 / 100	103 ms	7048 KiB

dna

#include<bits/stdc++.h>

using namespace std;

struct Node {
    int changes = 0;
    int at = 0, tc = 0, ca = 0;
} ;

typedef pair<int, int> pii;

constexpr int siz = (1 << 17); // 1 << 17

Node segment_tree[siz * 2 + 1];


void update(int pos, char a, char b)
{
    Node change = { (a != b), 
    (a == 'A' && b == 'T') - (b == 'A' && a == 'T'), 
    (a == 'T' && b == 'C') - (b == 'T' && a == 'C'), 
    (a == 'C' && b == 'A') - (b == 'C' && a == 'A')};
    if (change.changes == 0) return ;
    while (pos > 0) {
        segment_tree[pos].at += change.at;
        segment_tree[pos].tc += change.tc;
        segment_tree[pos].ca += change.ca;
        segment_tree[pos].changes += change.changes;
        
        pos /= 2;
    }
}



Node rangeq(int pos, pii wan, pii sear)
{
    // Out of interval
    if (wan.second < sear.first || sear.second < wan.first) 
        return Node{0,0,0,0};
    
    // All in interval
    if (wan.first <= sear.first && sear.second <= wan.second) 
        return segment_tree[pos];

    int mid = (sear.first + sear.second) / 2;
    Node left = rangeq(pos * 2, wan, pii(sear.first, mid)),
    right = rangeq(pos * 2 + 1, wan, pii(mid + 1, sear.second));
    
    left.at += right.at;
    left.tc += right.tc;
    left.ca += right.ca;
    left.changes += right.changes;
    return left;
}


int query(int x, int y)
{
    Node r = rangeq(1, pii(x, y), pii(0, siz - 1));

    if ((r.at != r.tc) || (r.ca != r.tc)) return -2;

    return r.changes + abs(r.at);
}




void init(string a, string b)
{
    for (int i = 0; i < a.size(); i++) {
        update(i + siz, a[i], b[i]);
    }
}

int get_distance(int x, int y)
{
    return query(x, y) / 2;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:72:23: 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: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16