oj.uz

Submission #937788

# Submission time Handle Problem Language Result Execution time Memory
937788 2024-03-04T13:11:01 Z Hanksburger Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1187 ms 48632 KB 
#include <bits/stdc++.h>
using namespace std;
string s[100005], t[100005], al[100005], ar[100005], bl[100005], br[100005];
map<string, int> amp, bmp;
pair<int, int> x[100005];
int y[405][305];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, acnt=0, bcnt=0, num=300;
    cin >> n >> m;
    for (int i=0; i<n; i++)
    {
        cin >> s[i];
        t[i]=s[i];
        reverse(t[i].begin(), t[i].end());
        amp[s[i]]=bmp[t[i]]=1;
    }
    for (int i=0; i<m; i++)
    {
        cin >> al[i] >> bl[i];
        reverse(bl[i].begin(), bl[i].end());
        ar[i]=al[i];
        br[i]=bl[i];
        ar[i].back()++;
        br[i].back()++;
        amp[al[i]]=amp[ar[i]]=bmp[bl[i]]=bmp[br[i]]=1;
    }
    for (auto it=amp.begin(); it!=amp.end(); it++)
        (*it).second=(++acnt);
    for (auto it=bmp.begin(); it!=bmp.end(); it++)
        (*it).second=(++bcnt);
    for (int i=0; i<n; i++)
        x[i]={amp[s[i]], bmp[t[i]]};
    sort(x, x+n);
    for (int i=0; i<=(n-1)/num; i++)
    {
        int l=i*num, r=min((i+1)*num-1, n-1);
        for (int j=l; j<=r; j++)
            y[i][j-l]=x[j].second;
        sort(y[i], y[i]+r-l+1);
    }
    for (int i=0; i<m; i++)
    {
        int AL=lower_bound(x, x+n, make_pair(amp[al[i]], 0))-x;
        int AR=lower_bound(x, x+n, make_pair(amp[ar[i]], 0))-x-1;
        int BL=bmp[bl[i]], BR=bmp[br[i]]-1, indl=AL/num, indr=AR/num, ans=0;
        if (indl==indr)
        {
            for (int j=AL; j<=AR; j++)
                if (x[j].second>=BL && x[j].second<=BR)
                    ans++;
        }
        else if (indl<indr)
        {
            for (int j=indl+1; j<indr; j++)
                ans+=upper_bound(y[j], y[j]+num, BR)-lower_bound(y[j], y[j]+num, BL);
            for (int j=AL; j<(indl+1)*num; j++)
                if (x[j].second>=BL && x[j].second<=BR)
                    ans++;
            for (int j=indr*num; j<=AR; j++)
                if (x[j].second>=BL && x[j].second<=BR)
                    ans++;
        }
        cout << ans << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20316 KB Output is correct
2 Correct 4 ms 20316 KB Output is correct
3 Correct 4 ms 20300 KB Output is correct
4 Correct 5 ms 20316 KB Output is correct
5 Correct 5 ms 20316 KB Output is correct
6 Correct 5 ms 20316 KB Output is correct
7 Correct 5 ms 20316 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 35676 KB Output is correct
2 Correct 53 ms 37968 KB Output is correct
3 Correct 41 ms 38224 KB Output is correct
4 Correct 46 ms 38064 KB Output is correct
5 Correct 44 ms 35668 KB Output is correct
6 Correct 49 ms 35680 KB Output is correct
7 Correct 46 ms 42580 KB Output is correct
8 Correct 56 ms 46068 KB Output is correct
9 Correct 71 ms 48632 KB Output is correct
10 Correct 36 ms 34032 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 20564 KB Output is correct
2 Correct 88 ms 20948 KB Output is correct
3 Correct 110 ms 21076 KB Output is correct
4 Correct 41 ms 21012 KB Output is correct
5 Correct 52 ms 20824 KB Output is correct
6 Correct 66 ms 21072 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20316 KB Output is correct
2 Correct 4 ms 20316 KB Output is correct
3 Correct 4 ms 20300 KB Output is correct
4 Correct 5 ms 20316 KB Output is correct
5 Correct 5 ms 20316 KB Output is correct
6 Correct 5 ms 20316 KB Output is correct
7 Correct 5 ms 20316 KB Output is correct
8 Correct 30 ms 35676 KB Output is correct
9 Correct 53 ms 37968 KB Output is correct
10 Correct 41 ms 38224 KB Output is correct
11 Correct 46 ms 38064 KB Output is correct
12 Correct 44 ms 35668 KB Output is correct
13 Correct 49 ms 35680 KB Output is correct
14 Correct 46 ms 42580 KB Output is correct
15 Correct 56 ms 46068 KB Output is correct
16 Correct 71 ms 48632 KB Output is correct
17 Correct 36 ms 34032 KB Output is correct
18 Correct 87 ms 20564 KB Output is correct
19 Correct 88 ms 20948 KB Output is correct
20 Correct 110 ms 21076 KB Output is correct
21 Correct 41 ms 21012 KB Output is correct
22 Correct 52 ms 20824 KB Output is correct
23 Correct 66 ms 21072 KB Output is correct
24 Correct 107 ms 37460 KB Output is correct
25 Correct 203 ms 38368 KB Output is correct
26 Correct 70 ms 37456 KB Output is correct
27 Correct 86 ms 37416 KB Output is correct
28 Correct 1187 ms 37244 KB Output is correct
29 Correct 129 ms 24148 KB Output is correct