algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

tle-oracle.cpp (888B)


      1 #include <vector>
      2 #include <iostream>
      3 
      4 using namespace std;
      5 
      6 int main() {
      7 
      8     int l, r, n, q, testCases = 0;
      9     cin >> testCases;
     10 
     11     for(int z = 0; z < testCases; ++z) {
     12         cin >> n;
     13         cin >> q;
     14 
     15         string a,b  = "";
     16 
     17         cin >> a;
     18         cin >> b;
     19 
     20         for(int qn = 0; qn < q; ++qn) {
     21             cin >> l;
     22             cin >> r;
     23 
     24             vector<int> countA (26,0);
     25             vector<int> countB (26,0);
     26 
     27             for(int i = l-1; i < r; ++i) {
     28                 countA[a[i] - 'a'] += 1;
     29                 countB[b[i] - 'a'] += 1;
     30             }
     31 
     32             int intersection = 0;
     33 
     34             for(int i = 0; i < countA.size(); ++i) {
     35                 int ca = countA[i];
     36                 int cb = countB[i];
     37                 intersection += std::min(ca,cb);
     38             }
     39 
     40             cout << ((r - l) + 1) - intersection << endl;
     41         }
     42 
     43 
     44     }
     45 
     46     
     47 
     48 }