oj.uz

Submission #937779

# Submission time Handle Problem Language Result Execution time Memory
937779 2024-03-04T12:59:16 Z Hanksburger Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 77 ms 39648 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;
    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)/300; i++)
    {
        int l=i*300, r=min(i*300+299, 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/300, indr=AR/300, 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]+300, BR)-lower_bound(y[j], y[j]+300, BL);
            for (int j=AL; j<indl*300; j++)
                if (x[j].second>=BL && x[j].second<=BR)
                    ans++;
            for (int j=indr*300; 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 5 ms 20352 KB Output is correct
3 Correct 5 ms 20316 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 20292 KB Output is correct
7 Correct 5 ms 20312 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20316 KB Output is correct
2 Correct 5 ms 20352 KB Output is correct
3 Correct 5 ms 20316 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 20292 KB Output is correct
7 Correct 5 ms 20312 KB Output is correct
8 Incorrect 32 ms 39648 KB Output isn't correct
9 Halted 0 ms 0 KB -