fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<unsigned long long> t;
  7. vector<unsigned long long> codes;
  8. const unsigned long long prime = 61;
  9. vector<unsigned  long long> pows;
  10.  
  11. void build (int v, int tl, int tr) {
  12.     if (tl == tr){
  13.         t[v] = codes[tl] * pows[tl - 1];
  14.     }
  15.     else {
  16.         int tm = (tl + tr) / 2;
  17.         build (2 * v, tl, tm);
  18.         build (2 * v + 1, tm + 1, tr);
  19.         t[v] = t[2 * v] + t[2 * v + 1];
  20.     }
  21. }
  22.  
  23. unsigned long long sum (int v, int tl, int tr, int l, int r) {
  24.     if (l > r){
  25.         //cout << "here";
  26.         return 0;
  27.     }
  28.     if (l == tl && r == tr)
  29.         return t[v];
  30.     int tm = (tl + tr) / 2;
  31.     return sum (2 * v, tl, tm, l, min(r, tm))
  32.            + sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
  33. }
  34.  
  35. void update (int v, int tl, int tr, int pos, unsigned long long newVal) {
  36.     if (tl == tr)
  37.         t[v] = newVal * pows[pos - 1];
  38.     else {
  39.         int tm = (tl + tr) / 2;
  40.         if (pos <= tm)
  41.             update (v*2, tl, tm, pos, newVal);
  42.         else
  43.             update (2 * v + 1, tm + 1, tr, pos, newVal);
  44.         t[v] = t[2 * v] + t[2 * v + 1];
  45.     }
  46. }
  47.  
  48. int main() {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.     int n, k;
  52.     cin >> n >> k;
  53.     t.resize(4 * n);
  54.     string a;
  55.     cin >> a;
  56.     codes.resize(n + 1);
  57.     for(int i = 1; i <= n; i++){
  58.         codes[i] = a[i - 1] - 'A' + 1;
  59.     }
  60.     pows.resize(n + 1);
  61.     pows[0] = 1;
  62.     for(int i = 1; i <= n; i++){
  63.         pows[i] = pows[i - 1] * prime;
  64.     }
  65.     build(1, 1, n);
  66.     cin.ignore();
  67.     for(int t = 0; t < k; t++){
  68.         char q;
  69.         cin >> q;
  70.         if(q == '?'){
  71.             int i, j, len;
  72.             cin >> i >> j >>len;
  73.             if(i > j){
  74.                 swap(i, j);
  75.             }
  76.             if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){
  77.                 cout << "+";
  78.             }
  79.             else{
  80.                 cout << "-";
  81.             }
  82.         }
  83.         else if(q == '*'){
  84.             int temp;
  85.             char c;
  86.             cin >> temp >> c;
  87.             update(1, 1, n, temp, c - 'A' + 1);
  88.         }
  89.         cin.ignore();
  90.     }
  91.     return 0;
  92. }
Runtime error #stdin #stdout 0s 4240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z2nEkp
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!