oj.uz

Submission #95151

# Submission time Handle Problem Language Result Execution time Memory
95151 2019-01-27T16:36:25 Z bogdan10bos Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 517 ms 301464 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 104580 KB Output is correct
2 Correct 109 ms 104516 KB Output is correct
3 Correct 109 ms 104440 KB Output is correct
4 Correct 92 ms 104440 KB Output is correct
5 Correct 100 ms 104568 KB Output is correct
6 Correct 92 ms 104460 KB Output is correct
7 Correct 92 ms 104488 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 263368 KB Output is correct
2 Correct 432 ms 255240 KB Output is correct
3 Correct 474 ms 261152 KB Output is correct
4 Correct 431 ms 253944 KB Output is correct
5 Correct 492 ms 298488 KB Output is correct
6 Correct 514 ms 301464 KB Output is correct
7 Correct 349 ms 110556 KB Output is correct
8 Correct 517 ms 223352 KB Output is correct
9 Correct 464 ms 204792 KB Output is correct
10 Correct 385 ms 199616 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 108660 KB Output is correct
2 Correct 144 ms 107568 KB Output is correct
3 Correct 153 ms 108280 KB Output is correct
4 Correct 139 ms 107228 KB Output is correct
5 Correct 145 ms 107416 KB Output is correct
6 Correct 142 ms 108040 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 104580 KB Output is correct
2 Correct 109 ms 104516 KB Output is correct
3 Correct 109 ms 104440 KB Output is correct
4 Correct 92 ms 104440 KB Output is correct
5 Correct 100 ms 104568 KB Output is correct
6 Correct 92 ms 104460 KB Output is correct
7 Correct 92 ms 104488 KB Output is correct
8 Correct 439 ms 263368 KB Output is correct
9 Correct 432 ms 255240 KB Output is correct
10 Correct 474 ms 261152 KB Output is correct
11 Correct 431 ms 253944 KB Output is correct
12 Correct 492 ms 298488 KB Output is correct
13 Correct 514 ms 301464 KB Output is correct
14 Correct 349 ms 110556 KB Output is correct
15 Correct 517 ms 223352 KB Output is correct
16 Correct 464 ms 204792 KB Output is correct
17 Correct 385 ms 199616 KB Output is correct
18 Correct 151 ms 108660 KB Output is correct
19 Correct 144 ms 107568 KB Output is correct
20 Correct 153 ms 108280 KB Output is correct
21 Correct 139 ms 107228 KB Output is correct
22 Correct 145 ms 107416 KB Output is correct
23 Correct 142 ms 108040 KB Output is correct
24 Correct 491 ms 235876 KB Output is correct
25 Correct 493 ms 236920 KB Output is correct
26 Correct 480 ms 234232 KB Output is correct
27 Correct 491 ms 234232 KB Output is correct
28 Correct 510 ms 133368 KB Output is correct
29 Correct 293 ms 114936 KB Output is correct