oj.uz

답안 #494863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494863 2021-12-16T21:24:57 Z Christopher_ Programiranje (COCI17_programiranje) C++17
80 / 80
 335 ms 17428 KB 
#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

# 결과 실행 시간 메모리 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