oj.uz

Submission #839441

# Submission time Handle Problem Language Result Execution time Memory
839441 2023-08-30T03:13:03 Z socpite Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 211024 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 2207;
const int base = 31;
const int sqr = 1300;

int n, q;

int cnt[maxn];

struct hashsus
{
    long long operator()(const pair<int, int> &a) const
    {
        return 1LL * mod * a.first + a.second;
    }
};

unordered_map<int, vector<int>> mp[2];
unordered_map<pair<int, int>, int, hashsus> mpq;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    string str;
    for (int i = 1; i <= n; i++)
    {
        cin >> str;
        if (str.size() >= sqr)
        {
            int val = 0;
            for (int j = 0; j < str.size(); j++)
            {
                auto v = str[j];
                val = (1LL * val * base + (v - 'A' + 1)) % mod;
                mp[0][val].push_back(i);
            }
            val = 0;
            for (int j = str.size() - 1; j >= 0; j--)
            {
                auto v = str[j];
                val = (1LL * val * base + (v - 'A' + 1)) % mod;
                mp[1][val].push_back(i);
            }
        }
        else
        {
            int pfx = 0;
            for (int j = 0; j < str.size(); j++)
            {
                pfx = (1LL * pfx * base + (str[j] - 'A' + 1)) % mod;
                int sfx = 0;
                for (int k = str.size() - 1; k >= 0; k--)
                {
                    sfx = (1LL * sfx * base + (str[k] - 'A' + 1)) % mod;
                    mpq[{pfx, sfx}]++;
                }
            }
        }
    }
    string P, Q;
    while (q--)
    {
        int pfx = 0, sfx = 0;
        cin >> P >> Q;
        for (int i = 0; i < P.size(); i++)
        {
            pfx = (1LL * pfx * base + P[i] - 'A' + 1) % mod;
        }
        for (int i = Q.size() - 1; i >= 0; i--)
        {
            sfx = (1LL * sfx * base + Q[i] - 'A' + 1) % mod;
        }
        vector<int> v1 = mp[0][pfx], v2 = mp[1][sfx];
        assert(v1.size() <= sqr);
        int ans = mpq[{pfx, sfx}];
        for (auto v : v1)
            cnt[v]++;
        for (auto v : v2)
            cnt[v]++;
        for (auto v : v1)
        {
            ans += (cnt[v] == 2);
        }
        for (auto v : v1)
            cnt[v]--;
        for (auto v : v2)
            cnt[v]--;
        cout << ans << "\n";
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:37:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int j = 0; j < str.size(); j++)
      |                             ~~^~~~~~~~~~~~
selling_rna.cpp:54:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int j = 0; j < str.size(); j++)
      |                             ~~^~~~~~~~~~~~
selling_rna.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < P.size(); i++)
      |                         ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 211024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 596 KB Output is correct
2 Correct 31 ms 3756 KB Output is correct
3 Correct 23 ms 1996 KB Output is correct
4 Correct 12 ms 460 KB Output is correct
5 Correct 31 ms 3684 KB Output is correct
6 Correct 24 ms 1968 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Execution timed out 1577 ms 211024 KB Time limit exceeded
9 Halted 0 ms 0 KB -