oj.uz

Submission #1079123

# Submission time Handle Problem Language Result Execution time Memory
1079123 2024-08-28T11:00:53 Z boris_mihov Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 998 ms 130056 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;
    // String()
    // {
    //     value = "";
    //     prefix.clear();
    // }

    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::min(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::min(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)
    {
        // std::cout << "here: " << i << '\n' << std::flush;
        String p, q;
        std::cin >> p.value >> q.value;
        // if (i < 6)
        // {
        //     continue;
        // }
        std::reverse(q.value.begin(), q.value.end());
        p.initalize(); q.initalize();
        
        int start, end;
        bool isOk = true;
        {
            int l = 0, r = n + 1, mid;
            while (l < r - 1)
            {
                mid = l + r >> 1;
                // if (i == 6) std::cout << "first binary: " << l << ' ' << r << ' ' << mid << ' ' << s[mid].isPrefix(p) << ' ' << (s[mid] < p) << '\n';
                if (s[mid].isPrefix(p))
                {
                    r = mid;
                    continue;
                }

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

        {
            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;
            isOk &= s[l].isPrefix(p);
        }

        if (end < start || !isOk)
        {
            // if (i == 6) std::cout << "not ok: " << start << ' ' << end << ' ' << isOk << ' ' << s[48].isPrefix(p) << "\n";
            continue;
        }


        // std::cout << "heeeree: " << start << ' ' << end << '\n';
        assert(start == 1 || !s[start - 1].isPrefix(p));
        assert(s[start].isPrefix(p));
        assert(s[end].isPrefix(p));
        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:63:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0 ; i < value.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool operator<(const String&, const String&)':
selling_rna.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |             mid = l + r >> 1;
      |                   ~~^~~
selling_rna.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   80 |         if (r == std::min(a.value.size(), b.value.size()))
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:127:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |                 mid = l + r >> 1;
      |                       ~~^~~
selling_rna.cpp:147:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  147 |                 mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 126712 KB Output is correct
2 Correct 994 ms 123716 KB Output is correct
3 Correct 88 ms 42728 KB Output is correct
4 Correct 87 ms 42736 KB Output is correct
5 Correct 525 ms 79352 KB Output is correct
6 Correct 478 ms 82552 KB Output is correct
7 Correct 106 ms 39504 KB Output is correct
8 Correct 315 ms 76288 KB Output is correct
9 Correct 294 ms 72636 KB Output is correct
10 Correct 259 ms 69380 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14824 KB Output is correct
2 Correct 35 ms 13764 KB Output is correct
3 Correct 40 ms 14260 KB Output is correct
4 Correct 36 ms 13320 KB Output is correct
5 Correct 36 ms 13268 KB Output is correct
6 Correct 50 ms 13796 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 998 ms 126712 KB Output is correct
9 Correct 994 ms 123716 KB Output is correct
10 Correct 88 ms 42728 KB Output is correct
11 Correct 87 ms 42736 KB Output is correct
12 Correct 525 ms 79352 KB Output is correct
13 Correct 478 ms 82552 KB Output is correct
14 Correct 106 ms 39504 KB Output is correct
15 Correct 315 ms 76288 KB Output is correct
16 Correct 294 ms 72636 KB Output is correct
17 Correct 259 ms 69380 KB Output is correct
18 Correct 49 ms 14824 KB Output is correct
19 Correct 35 ms 13764 KB Output is correct
20 Correct 40 ms 14260 KB Output is correct
21 Correct 36 ms 13320 KB Output is correct
22 Correct 36 ms 13268 KB Output is correct
23 Correct 50 ms 13796 KB Output is correct
24 Correct 931 ms 127460 KB Output is correct
25 Correct 929 ms 130056 KB Output is correct
26 Correct 713 ms 126712 KB Output is correct
27 Correct 99 ms 48044 KB Output is correct
28 Correct 278 ms 65272 KB Output is correct
29 Correct 170 ms 36796 KB Output is correct