oj.uz

답안 #1079086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079086 2024-08-28T10:32:52 Z boris_mihov Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1059 ms 128672 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;
        }
        // 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8260 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 4 ms 8536 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8236 KB Output is correct
6 Correct 4 ms 8276 KB Output is correct
7 Correct 4 ms 8200 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1059 ms 128672 KB Output is correct
2 Correct 1004 ms 125480 KB Output is correct
3 Correct 88 ms 44552 KB Output is correct
4 Correct 99 ms 44740 KB Output is correct
5 Incorrect 449 ms 80252 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 14900 KB Output is correct
2 Correct 31 ms 13656 KB Output is correct
3 Correct 34 ms 14532 KB Output is correct
4 Correct 38 ms 13348 KB Output is correct
5 Correct 35 ms 13256 KB Output is correct
6 Correct 57 ms 14024 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8260 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 4 ms 8536 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 4 ms 8236 KB Output is correct
6 Correct 4 ms 8276 KB Output is correct
7 Correct 4 ms 8200 KB Output is correct
8 Correct 1059 ms 128672 KB Output is correct
9 Correct 1004 ms 125480 KB Output is correct
10 Correct 88 ms 44552 KB Output is correct
11 Correct 99 ms 44740 KB Output is correct
12 Incorrect 449 ms 80252 KB Output isn't correct
13 Halted 0 ms 0 KB -