Submission #937779

#	Time	Username	Problem	Language	Result	Execution time	Memory
937779		Hanksburger	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	77 ms	39648 KiB

selling_rna

#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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40