src/test/aoj_2907.cpp

View this file on GitHub
Last update: 2025-10-08 00:44:44+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2907

Depends on

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2907
#include "../merge_sort_tree.hpp"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<string> S(N);
    rep(i, N) cin >> S[i];
    sort(all(S));
    vector<string> T = S;
    rep(i, N) reverse(all(T[i]));
    merge_sort_tree<string> tree(T);
    rep(i, Q) {
        string p, s;
        cin >> p >> s;
        int l = lower_bound(all(S), p) - S.begin();
        p += "|";
        int r = lower_bound(all(S), p) - S.begin();
        reverse(all(s));
        int ans = 0;
        ans -= tree.range_cnt(l, r, s);
        s += '|';
        ans += tree.range_cnt(l, r, s);
        cout << ans << "\n";
    }
}

#line 1 "src/test/aoj_2907.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2907
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/merge_sort_tree.hpp"

template<class S, bool EnableSum = 0> struct merge_sort_tree {
    int n;
    vector<vector<S>> d, s;
    merge_sort_tree(vector<S>& a): n(__bit_ceil(si(a))), d(n * 2), s(n * 2) {
        rep(i, si(a)) d[n + i] = {a[i]}, s[n + i] = {S(), a[i]};
        for(int i = n; --i;) {
            merge(all(d[i * 2]), all(d[i * 2 + 1]), back_inserter(d[i]));
            if(!EnableSum) continue;
            s[i].resize(si(d[i]) + 1, S());
            rep(j, si(d[i])) s[i][j + 1] = s[i][j] + d[i][j];
        }
    }
    int range_cnt(int l, int r, S& u) {
        int ret = 0;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ret += lower_bound(all(d[l]), u) - d[l].begin(), l++;
            if(r & 1) --r, ret += lower_bound(all(d[r]), u) - d[r].begin();
        }
        return ret;
    }
    S range_sum(int l, int r, S& u) {
        assert(EnableSum);
        S ret = 0;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ret += s[l][lower_bound(all(d[l]), u) - d[l].begin()], l++;
            if(r & 1) --r, ret += s[r][lower_bound(all(d[r]), u) - d[r].begin()];
        }
        return ret;
    }
};
#line 3 "src/test/aoj_2907.cpp"

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<string> S(N);
    rep(i, N) cin >> S[i];
    sort(all(S));
    vector<string> T = S;
    rep(i, N) reverse(all(T[i]));
    merge_sort_tree<string> tree(T);
    rep(i, Q) {
        string p, s;
        cin >> p >> s;
        int l = lower_bound(all(S), p) - S.begin();
        p += "|";
        int r = lower_bound(all(S), p) - S.begin();
        reverse(all(s));
        int ans = 0;
        ans -= tree.range_cnt(l, r, s);
        s += '|';
        ans += tree.range_cnt(l, r, s);
        cout << ans << "\n";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	0_sample_01	AC	5 ms	4 MB
g++	0_sample_02	AC	4 ms	4 MB
g++	0_sample_03	AC	4 ms	4 MB
g++	10_english_01	AC	20 ms	4 MB
g++	10_english_02	AC	45 ms	4 MB
g++	10_english_03	AC	43 ms	4 MB
g++	20_test_01	AC	8 ms	4 MB
g++	20_test_02	AC	18 ms	17 MB
g++	20_test_03	AC	282 ms	92 MB
g++	20_test_04	AC	291 ms	90 MB
g++	20_test_05	AC	223 ms	56 MB
g++	20_test_06	AC	215 ms	56 MB
g++	20_test_07	AC	18 ms	17 MB
g++	20_test_08	AC	294 ms	92 MB
g++	20_test_09	AC	690 ms	157 MB
g++	20_test_10	AC	301 ms	157 MB
g++	20_test_11	AC	344 ms	91 MB
g++	20_test_12	AC	55 ms	40 MB
clang++	0_sample_01	AC	5 ms	4 MB
clang++	0_sample_02	AC	4 ms	4 MB
clang++	0_sample_03	AC	4 ms	4 MB
clang++	10_english_01	AC	22 ms	4 MB
clang++	10_english_02	AC	48 ms	4 MB
clang++	10_english_03	AC	46 ms	4 MB
clang++	20_test_01	AC	9 ms	4 MB
clang++	20_test_02	AC	20 ms	17 MB
clang++	20_test_03	AC	281 ms	92 MB
clang++	20_test_04	AC	291 ms	91 MB
clang++	20_test_05	AC	220 ms	56 MB
clang++	20_test_06	AC	225 ms	56 MB
clang++	20_test_07	AC	18 ms	17 MB
clang++	20_test_08	AC	275 ms	91 MB
clang++	20_test_09	AC	659 ms	157 MB
clang++	20_test_10	AC	295 ms	158 MB
clang++	20_test_11	AC	368 ms	91 MB
clang++	20_test_12	AC	55 ms	40 MB