Submission #981134

#	Time	Username	Problem	Language	Result	Execution time	Memory
981134		aaaaaarroz	Mutating DNA (IOI21_dna)	C++17	100 / 100	135 ms	28752 KiB

dna

#include <bits/stdc++.h>
using namespace std;
struct letras{
	int a, t, c;
};
struct con{
	int at,ac,ta,tc,ca,ct;
};
template<class T, T m_(T, T)> struct IterativeSegmentTree{
  int n; vector<T> ST;
  IterativeSegmentTree(){}
  IterativeSegmentTree(vector<T> &a){
    n = a.size(); ST.resize(n << 1);
    for (int i=n;i<(n<<1);i++)ST[i]=a[i-n];
    for (int i=n-1;i>0;i--)ST[i]=m_(ST[i<<1],ST[i<<1|1]);
  }
  void update(int pos, T val){ // replace with val
    ST[pos += n] = val;
    for (pos >>= 1; pos > 0; pos >>= 1)
      ST[pos] = m_(ST[pos<<1], ST[pos<<1|1]);
  }
  T query(int l, int r){ // [l, r]
    T ansL, ansR; bool hasL = 0, hasR = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) 
        ansL=(hasL?m_(ansL,ST[l++]):ST[l++]),hasL=1;
      if (r & 1) 
        ansR=(hasR?m_(ST[--r],ansR):ST[--r]),hasR=1;
    }
    if (!hasL) return ansR; if (!hasR) return ansL;
    return m_(ansL, ansR);
  }
}; // Give vector of leaves and merge function

int merge(int a, int b){
    return a+b;
}

letras merge2(letras a, letras b){
  letras c;
  c.a=a.a+b.a;
  c.t=a.t+b.t;
  c.c=a.c+b.c;
  return c;
}

con merge3(con a, con b){
  con c;
  c.at=a.at+b.at;
  c.ac=a.ac+b.ac;
  c.ta=a.ta+b.ta;
  c.tc=a.tc+b.tc;
  c.ca=a.ca+b.ca;
  c.ct=a.ct+b.ct;
  return c;
}


vector<int>aaa;
IterativeSegmentTree<int,merge>st(aaa);
vector<letras>bbb;
IterativeSegmentTree<letras,merge2>la(bbb);
IterativeSegmentTree<letras,merge2>lb(bbb);
vector<con>ccc;
IterativeSegmentTree<con,merge3>cc(ccc);
void init(string a, string b){
	vector<int>diff(a.length());
	for(int i=0;i<a.length();i++){
		if(a[i]!=b[i])diff[i]=1;
		else diff[i]=0;
	}
	IterativeSegmentTree<int,merge>s(diff);
	st=s;
  vector<letras>aa(a.length());
  vector<letras>bb(b.length());
  for(int i=0;i<a.length();i++){
		if(a[i]=='C')aa[i].c=1;
    else if(a[i]=='A')aa[i].a=1;
    else if(a[i]=='T')aa[i].t=1;
    if(b[i]=='C')bb[i].c=1;
    else if(b[i]=='A')bb[i].a=1;
    else if(b[i]=='T')bb[i].t=1;
	}
  IterativeSegmentTree<letras,merge2>cla(aa);
  IterativeSegmentTree<letras,merge2>clb(bb);
  la=cla;
  lb=clb;
  vector<con>ccccc(a.length());
  for(int i=0;i<a.length();i++){
    con c;
    c.at=0;
    c.ac=0;
    c.ta=0;
    c.tc=0;
    c.ca=0;
    c.ct=0;
		if(a[i]=='A'&&b[i]=='C'){
      c.ac=1;
    }
    else if(a[i]=='A'&&b[i]=='T'){
      c.at=1;
    }
    else if(a[i]=='T'&&b[i]=='C'){
      c.tc=1;
    }
    else if(a[i]=='T'&&b[i]=='A'){
      c.ta=1;
    }
    else if(a[i]=='C'&&b[i]=='T'){
      c.ct=1;
    }
    else if(a[i]=='C'&&b[i]=='A'){
      c.ca=1;
    }
    ccccc[i]=c;
	}
  IterativeSegmentTree<con,merge3>cccc(ccccc);
  cc=cccc;
}
int get_distance(int x, int y){
  if(la.query(x,y).a!=lb.query(x,y).a||la.query(x,y).c!=lb.query(x,y).c||la.query(x,y).t!=lb.query(x,y).t){
    return -1;
  }
  else{
    int sum=0;
    con q=cc.query(x,y);
    int min_ca=min(q.ac,q.ca);
    int max_ca=max(q.ac,q.ca);
    sum+=min_ca;
    int min_at=min(q.at,q.ta);
    int max_at=max(q.at,q.ta);
    sum+=min_at;
    int min_ct=min(q.tc,q.ct);
    int max_ct=max(q.tc,q.ct);
    sum+=min_ct;
    sum+=((max_ct-min_ct)*2);
    return sum;
  }
}

Compilation message (stderr)

dna.cpp: In member function 'T IterativeSegmentTree<T, m_>::query(int, int)':
dna.cpp:30:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   30 |     if (!hasL) return ansR; if (!hasR) return ansL;
      |     ^~
dna.cpp:30:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   30 |     if (!hasL) return ansR; if (!hasR) return ansL;
      |                             ^~
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=0;i<a.length();i++){
      |              ~^~~~~~~~~~~
dna.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i=0;i<a.length();i++){
      |               ~^~~~~~~~~~~
dna.cpp:89:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int i=0;i<a.length();i++){
      |               ~^~~~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:128:9: warning: unused variable 'max_ca' [-Wunused-variable]
  128 |     int max_ca=max(q.ac,q.ca);
      |         ^~~~~~
dna.cpp:131:9: warning: unused variable 'max_at' [-Wunused-variable]
  131 |     int max_at=max(q.at,q.ta);
      |         ^~~~~~

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