oj.uz

Submission #112509

# Submission time Handle Problem Language Result Execution time Memory
112509 2019-05-20T11:19:05 Z Kastanda Selling RNA Strands (JOI16_selling_rna) C++11
0 / 100
 108 ms 18116 KB 
#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 += upper_bound(vec[l].begin(), vec[l].end(), ri) - lower_bound(vec[l].begin(), vec[l].end(), le), l ++;
        if (r & 1) r --, ret += upper_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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 11264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 17776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 18116 KB Output is correct
2 Incorrect 79 ms 15224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 11264 KB Output isn't correct
2 Halted 0 ms 0 KB -