Submission #494863

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
494863	2021-12-16T21:24:57 Z	Christopher_	Programiranje (COCI17_programiranje)	C++17	80 / 80	335 ms	17428 KB

programiranje

#include <bits/stdc++.h>

using namespace std;

struct SegTree {
  struct Node {
    vector<int> cnt;
  };
  int n;
  string s;
  vector<Node> tree;
  SegTree(const string &S) {
    // cerr << 13 << '\n';
    n = (int) S.size();
    s = S;
    tree.resize(4 * n);
    build(0, 0, n - 1);
  }
  vector<int> merge(vector<int> &a, vector<int> &b) {
    // cerr << 18 << '\n';
    vector<int> res(26, 0);
    for (int i = 0; i < 26; ++i) {
      res[i] = a[i] + b[i];
    }
    return res;
  }
  void build(int x, int l, int r) {
    // cerr << x << ' ' << l << ' ' << r << '\n';
    // cerr << 27 << '\n';
    if (l == r) {
      // cerr << 30 << '\n';
      tree[x].cnt.resize(26);
      // cerr << 31 << '\n';
      ++tree[x].cnt[(int) (s[l] - 'a')];
      return;
    }
    int m = (l + r) >> 1;
    // cerr << 34 << '\n';
    build((x << 1) + 1, l, m);
    build((x << 1) + 2, m + 1, r);
    // cerr << 37 << '\n';
    tree[x].cnt = merge(tree[(x << 1) + 1].cnt, tree[(x << 1) + 2].cnt);
  }
  vector<int> get(int x, int l, int r, int tl, int tr) {
    // cerr << 45 << '\n';
    if (r < tl || l > tr) return vector<int>(26, 0);
    else if (l >= tl && r <= tr) {
      return tree[x].cnt;
    }
    int m = (l + r) >> 1;
    vector<int> a = get((x << 1) + 1, l, m, tl, tr);
    vector<int> b = get((x << 1) + 2, m + 1, r, tl, tr);
    return merge(a, b);
  }
  vector<int> get(int a, int b) {
    return get(0, 0, n - 1, a, b);
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  SegTree st(s);
  // cerr << 51 << '\n';
  int q;
  cin >> q;
  while (q--) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a, --b, --c, --d;
    vector<int> A = st.get(a, b);
    vector<int> B = st.get(c, d);
    if (A == B) {
      cout << "DA\n";
    } else {
      cout << "NE\n";
    }
  }
}

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	640 KB	Output is correct
2	Correct	4 ms	628 KB	Output is correct
3	Correct	4 ms	588 KB	Output is correct
4	Correct	5 ms	632 KB	Output is correct
5	Correct	4 ms	588 KB	Output is correct
6	Correct	332 ms	17320 KB	Output is correct
7	Correct	335 ms	17428 KB	Output is correct
8	Correct	310 ms	17328 KB	Output is correct
9	Correct	326 ms	17428 KB	Output is correct
10	Correct	319 ms	17312 KB	Output is correct