oj.uz

Submission #1079089

# Submission time Handle Problem Language Result Execution time Memory
1079089 2024-08-28T10:36:19 Z boris_mihov Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 937 ms 129868 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 || (a.value1 == b.value1 && a.value2 < b.value2);
        }

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

    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;
        }

        assert(start == 1 || !s[start - 1].isPrefix(p));
        assert(s[start].isPrefix(p));
        assert(s[end].isPrefix(p));
        // 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 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 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 923 ms 129868 KB Output is correct
2 Correct 937 ms 126640 KB Output is correct
3 Correct 97 ms 45604 KB Output is correct
4 Correct 86 ms 45648 KB Output is correct
5 Incorrect 439 ms 81140 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 39 ms 14900 KB Output is correct
2 Correct 27 ms 13852 KB Output is correct
3 Correct 32 ms 14532 KB Output is correct
4 Correct 28 ms 13320 KB Output is correct
5 Correct 40 ms 13424 KB Output is correct
6 Correct 37 ms 14104 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 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 923 ms 129868 KB Output is correct
9 Correct 937 ms 126640 KB Output is correct
10 Correct 97 ms 45604 KB Output is correct
11 Correct 86 ms 45648 KB Output is correct
12 Incorrect 439 ms 81140 KB Output isn't correct
13 Halted 0 ms 0 KB -