제출 #112510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112510		Kastanda	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	463 ms	31544 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q, P[N];
string S[N], R[N];
vector < int > vec[N * 2];
bool CMP(int i, int j)
{
    return (R[i] < R[j]);
}
inline int Get(int l, int r, int le, int ri)
{
    int ret = 0;
    l += n; r += n;
    for (; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1) ret += lower_bound(vec[l].begin(), vec[l].end(), ri) - lower_bound(vec[l].begin(), vec[l].end(), le), l ++;
        if (r & 1) r --, ret += lower_bound(vec[r].begin(), vec[r].end(), ri) - lower_bound(vec[r].begin(), vec[r].end(), le);
    }
    return (ret);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i ++)
        cin >> S[i], P[i] = i;
    sort(S, S + n);
    for (int i = 0; i < n; i ++)
        R[i] = S[i], reverse(R[i].begin(), R[i].end());
    sort(P, P + n, CMP);
    for (int i = 0; i < n; i ++)
        for (int id = i + n; id; id >>= 1)
            vec[id].push_back(P[i]);
    for (int i = 0; i < n + n; i ++)
        sort(vec[i].begin(), vec[i].end());
    for (int i = 0; i < q; i ++)
    {
        string A, B;
        cin >> A >> B;
        int l = lower_bound(S, S + n, A) - S;
        A.back() ++;
        int r = lower_bound(S, S + n, A) - S;
        reverse(B.begin(), B.end());
        R[n] = B;
        int le = lower_bound(P, P + n, n, CMP) - P;
        B.back() ++; R[n] = B;
        int ri = lower_bound(P, P + n, n, CMP) - P;
        printf("%d\n", Get(le, ri, l, r));
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40