Submission #95151

#	Time	Username	Problem	Language	Result	Execution time	Memory
95151		bogdan10bos	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	517 ms	301464 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;

const int NMAX = 1e5;
const int LMAX = 2e6;

int N, M, I;
int sol[NMAX + 5];
pii itvy[NMAX + 5];
vector<int> pos[NMAX + 5];
vector<int> upd[LMAX + 5], qry[LMAX + 5];

int getid(char ch)
{
    if(ch == 'A')   return 0;
    if(ch == 'G')   return 1;
    if(ch == 'C')   return 2;
    if(ch == 'U')   return 3;
    return -1;
}

class Trie
{
public:
    Trie *nxt[4];
    int itv[2];
    vector<int> who;

    Trie() { nxt[0] = nxt[1] = nxt[2] = nxt[3] = 0; itv[0] = itv[1] = 0; }
};

Trie *root[2];

void insert(Trie *T, string s, int id)
{
    for(auto ch: s)
    {
        int x = getid(ch);
        if(T->nxt[x] == 0)  T->nxt[x] = new Trie();
        T = T->nxt[x];
    }
    T->who.push_back(id);
}

void DFS(Trie *T)
{
    T->itv[0] = ++I;
    for(int i = 0; i < 4; i++)
        if(T->nxt[i])
            DFS(T->nxt[i]);
    T->itv[1] = I;
    for(auto x: T->who)
        pos[x].push_back(T->itv[0]);
}

pii query(Trie *T, string s)
{
    for(auto ch: s)
    {
        int x = getid(ch);
        if(T->nxt[x] == 0)  return {-1, -1};
        T = T->nxt[x];
    }
    return {T->itv[0], T->itv[1]};
}

class BinaryIndexedTree
{
public:
    int N;
    vector<int> aib;
    void init(int N)
    {
        aib.resize(N + 5);
    }

    void U(int pos, int val)
    {
        for(; pos < aib.size(); pos += (pos & (-pos)))
            aib[pos] += val;
    }

    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }
}aib;

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    cin >> N >> M;

    root[0] = new Trie();
    root[1] = new Trie();
    for(int i = 1; i <= N; i++)
    {
        string s;
        cin >> s;
        insert(root[0], s, i);
        reverse(s.begin(), s.end());
        insert(root[1], s, i);
    }

    I = 0;
    DFS(root[0]);
    I = 0;
    DFS(root[1]);

    for(int i = 1; i <= N; i++)
        upd[ pos[i][0] ].push_back(pos[i][1]);

    for(int i = 1; i <= M; i++)
    {
        string pfx, sfx;
        cin >> pfx >> sfx;
        pii x = query(root[0], pfx);
        reverse(sfx.begin(), sfx.end());
        pii y = query(root[1], sfx);

        if(x.first != -1 && y.first != -1)
        {
            qry[x.first - 1].push_back(-i);
            qry[x.second].push_back(i);
            itvy[i] = y;
        }
    }

    aib.init(LMAX);
    for(int i = 1; i <= LMAX; i++)
    {
        for(auto x: upd[i])
            aib.U(x, 1);
        for(auto id: qry[i])
        {
            int smn = 1;
            if(id < 0) id = -id, smn = -1;
            int val = aib.Q(itvy[id].second) - aib.Q(itvy[id].first - 1);
            sol[id] += smn * val;
        }
    }

    for(int i = 1; i <= M; i++)
        printf("%d\n", sol[i]);

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void BinaryIndexedTree::U(int, int)':
selling_rna.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pos < aib.size(); pos += (pos & (-pos)))
               ~~~~^~~~~~~~~~~~

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