oj.uz

Submission #1079083

# Submission time Handle Problem Language Result Execution time Memory
1079083 2024-08-28T10:31:06 Z boris_mihov Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 880 ms 126396 KB 
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD1 = 1000003013;
const int MOD2 = 1000003241;
const int BASE = 5;

int n, q;
int decode[256];
// int base1[MAXN];
// int base2[MAXN];
struct String
{
    std::string value;
    struct Hash
    {
        llong value1, value2;
        Hash()
        {
            value1 = value2 = 0;
        }
        
        void push(char letter)
        {
            value1 *= BASE;
            value2 *= BASE;
            value1 += decode[letter];
            value2 += decode[letter];
            value1 %= MOD1;
            value2 %= MOD2;
        }

        friend bool operator < (const Hash &a, const Hash &b)
        {
            return a.value1 < b.value1;
        }

        friend bool operator == (const Hash &a, const Hash &b)
        {
            return a.value1 == b.value1;
        }
    };

    std::vector <Hash> prefix;
    void initalize()
    {
        Hash curr;
        prefix.reserve(value.size());
        for (int i = 0 ; i < value.size() ; ++i)
        {
            curr.push(value[i]);
            prefix.push_back(curr);
        }
    }

    friend bool operator < (const String &a, const String &b)
    {
        int l = -1, r = std::max(a.value.size(), b.value.size()), mid;
        while (l < r - 1)
        {
            mid = l + r >> 1;
            if (a.prefix[mid] == b.prefix[mid]) l = mid;
            else r = mid;
        }

        if (r == std::max(a.value.size(), b.value.size()))
        {
            return a.value.size() < b.value.size();
        }

        return a.value[r] < b.value[r];
    }

    bool isPrefix(const String &a)
    {
        if (a.value.size() <= value.size() && a.prefix.back() == prefix[a.value.size() - 1]) return true;
        return false;
    }
};

String s[MAXN];
struct Query
{
    char type;
    String::Hash hash;
    int idx;
};

int output[MAXN];
std::vector <Query> queries[MAXN];

void solve()
{
    std::sort(s + 1, s + 1 + n);
    for (int i = 1 ; i <= q ; ++i)
    {
        String p, q;
        std::cin >> p.value >> q.value;
        std::reverse(q.value.begin(), q.value.end());
        p.initalize(); q.initalize();
        
        int start, end;
        {
            int l = 0, r = n + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                if (s[mid].isPrefix(p))
                {
                    r = mid;
                    continue;
                }

                if (s[mid] < p) l = mid;
                else r = mid;
            }
            
            start = r;
        }

        {
            int l = 0, r = n + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                // std::cout << "here: " << p.value << ' ' << s[mid].value << ' ' << l << ' ' << r << ' ' << mid << ' ' << (p.value < s[mid].value) << '\n';
                if (s[mid].isPrefix(p))
                {
                    l = mid;
                    continue;
                }

                if (s[mid] < p) l = mid;
                else r = mid;
            }
            
            end = l;
        }

        if (end < start)
        {
            continue;
        }
        // std::cout << "start end: " << p.value << ' ' << start << ' ' << end << '\n';
        queries[start - 1].push_back({'-', q.prefix.back(), i});
        queries[end].push_back({'+', q.prefix.back(), i});
    }

    std::unordered_map <llong, int> cnt;
    for (int i = 1 ; i <= n ; ++i)
    {
        String::Hash curr;
        for (int j = s[i].value.size() - 1 ; j >= 0 ; --j)
        {
            curr.push(s[i].value[j]);
            cnt[curr.value1 * MOD1 + curr.value2]++;
        }

        for (const auto &[type, h, idx] : queries[i])
        {
            if (type == '-') output[idx] -= cnt[h.value1 * MOD1 + h.value2];
            else output[idx] += cnt[h.value1 * MOD1 + h.value2];
        }
    }
}

void input()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> s[i].value;
        s[i].initalize();
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << output[i] << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

void initialize()
{
    decode['A'] = 1;
    decode['C'] = 2;
    decode['G'] = 3;
    decode['U'] = 4;

    // base1[0] = base2[0] = 1;
    // for (int i = 1 ; i < MAXN ; ++i)
    // {
    //     base1[i] = (1LL * base1[i - 1] * BASE) % MOD1;
    //     base2[i] = (1LL * base2[i - 1] * BASE) % MOD2;
    // }
}

int main()
{
    initialize();
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message

selling_rna.cpp: In member function 'void String::Hash::push(char)':
selling_rna.cpp:34:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   34 |             value1 += decode[letter];
      |                              ^~~~~~
selling_rna.cpp:35:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |             value2 += decode[letter];
      |                              ^~~~~~
selling_rna.cpp: In member function 'void String::initalize()':
selling_rna.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0 ; i < value.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool operator<(const String&, const String&)':
selling_rna.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |             mid = l + r >> 1;
      |                   ~~^~~
selling_rna.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   73 |         if (r == std::max(a.value.size(), b.value.size()))
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:114:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |                 mid = l + r >> 1;
      |                       ~~^~~
selling_rna.cpp:132:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |                 mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 126396 KB Output is correct
2 Correct 880 ms 123300 KB Output is correct
3 Correct 83 ms 42324 KB Output is correct
4 Correct 86 ms 42320 KB Output is correct
5 Incorrect 409 ms 78832 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14640 KB Output is correct
2 Correct 28 ms 13512 KB Output is correct
3 Correct 30 ms 14020 KB Output is correct
4 Correct 27 ms 13068 KB Output is correct
5 Correct 30 ms 13008 KB Output is correct
6 Correct 36 ms 13508 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8280 KB Output is correct
2 Correct 4 ms 8280 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 875 ms 126396 KB Output is correct
9 Correct 880 ms 123300 KB Output is correct
10 Correct 83 ms 42324 KB Output is correct
11 Correct 86 ms 42320 KB Output is correct
12 Incorrect 409 ms 78832 KB Output isn't correct
13 Halted 0 ms 0 KB -