oj.uz

Submission #1005832

# Submission time Handle Problem Language Result Execution time Memory
1005832 2024-06-23T06:46:15 Z Ice_man Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 158 ms 298904 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>

#define maxn 2000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;


typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , ll> pil;
typedef pair <ll , int> pli;
typedef long double pd;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}

struct query
{
    int idx;
    int l , r;
    int x;

    query(){};
    query(int _idx, int _l , int _r , int _x)
    {
        idx = _idx;
        l = _l;
        r = _r;
        x = _x;
    }
};

struct Fenwick
{
    vector <int> fenwick;
    int sz;

    void _set(int _sz)
    {
        fenwick.resize(_sz + 1);
        sz = _sz;
    }

    void update(int qpos , int qval)
    {
        for(int i = qpos; i <= sz; i += (i & -i))
            fenwick[i] += qval;
    }

    int query(int qpos)
    {
        int ans = 0;
        for(int i = qpos; i >= 1; i -= (i & -i))
            ans += fenwick[i];
        return ans;
    }
};

int get_num(char c)
{
    if(c == 'A')
        return 0;
    else
        if(c == 'G')
            return 1;
        else
            if(c == 'C')
                return 2;
            else
                return 3; /// U
}


int sz[2] = {1 , 1} , nb[2][maxn][4];
int timer[2] = {0 , 0} , l[2][maxn] , r[2][maxn];

int _find(bool t , string &s)
{
    int node = 0;
    for(char &c : s)
    {
        int id = get_num(c);
        if(nb[t][node][id] == 0)
            return -1;
        node = nb[t][node][id];
    }
    return node;
}


void add(bool t , string &s)
{
    int node = 0;
    for(char &c : s)
    {
        int id = get_num(c);
        if(nb[t][node][id] == 0)
            nb[t][node][id] = sz[t]++;
        node = nb[t][node][id];
    }
}

void dfs(bool t , int node)
{
    l[t][node] = timer[t];
    timer[t]++;

    for(int i = 0; i < 4; i++)
        if(nb[t][node][i] != 0)
            dfs(t , nb[t][node][i]);

    r[t][node] = timer[t];
}


int n , q;
string s[maxn];
string rev[maxn];

void read()
{
    cin >> n >> q;
    for(int i = 0; i < n; i++)
    {
        cin >> s[i];

        add(0 , s[i]);
        rev[i] = s[i];
        reverse(rev[i].begin() , rev[i].end());
        add(1 , rev[i]);
    }

    dfs(0 , 0);
    dfs(1 , 0);
}

vector <int> points[maxn];

void make_points()
{
    for(int i = 0; i < n; i++)
    {
        int pom0 = l[0][_find(0 , s[i])];
        int pom1 = l[1][_find(1 , rev[i])];
        //cout << "-> " << pom1 << " " << pom0 << endl;
        points[pom1].pb(pom0);
    }
}

int ans[maxn];
string su , p;
vector <query> qu[maxn];

void solve()
{
    for(int i = 0; i < q; i++)
    {
        cin >> p >> su;
        reverse(su.begin() , su.end());

        int idp = _find(0 , p);
        int idsu = _find(1 , su);

        if(idp == -1 || idsu == -1)
            continue;

        qu[l[1][idsu]].push_back({i , l[0][idp] , r[0][idp] , -1});
        qu[r[1][idsu]].push_back({i , l[0][idp] , r[0][idp] , 1});
    }

    Fenwick f;
    f._set(maxn);
    for(int i = 1; i < maxn; i++)
    {
        for(int j : points[i - 1])
            f.update(j + 1 , 1);

        for(query j : qu[i])
            ans[j.idx] += j.x * (f.query(j.r) - f.query(j.l));
    }

    for(int i = 0; i < q; i++)
        cout << ans[i] << endl;
}




int main()
{

/**#ifdef ONLINE_JUDGE /// promeni
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
#endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();
    make_points();
    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 236124 KB Output is correct
2 Correct 41 ms 236124 KB Output is correct
3 Correct 41 ms 236124 KB Output is correct
4 Correct 38 ms 236112 KB Output is correct
5 Correct 44 ms 236112 KB Output is correct
6 Correct 38 ms 236200 KB Output is correct
7 Correct 39 ms 236124 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 285268 KB Output is correct
2 Correct 106 ms 287224 KB Output is correct
3 Correct 115 ms 287408 KB Output is correct
4 Correct 106 ms 285780 KB Output is correct
5 Correct 133 ms 298068 KB Output is correct
6 Correct 158 ms 298904 KB Output is correct
7 Correct 82 ms 245120 KB Output is correct
8 Correct 126 ms 279124 KB Output is correct
9 Correct 102 ms 275536 KB Output is correct
10 Correct 95 ms 272332 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 238520 KB Output is correct
2 Correct 57 ms 238148 KB Output is correct
3 Correct 59 ms 238420 KB Output is correct
4 Correct 57 ms 238028 KB Output is correct
5 Correct 53 ms 238324 KB Output is correct
6 Correct 64 ms 238904 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 236124 KB Output is correct
2 Correct 41 ms 236124 KB Output is correct
3 Correct 41 ms 236124 KB Output is correct
4 Correct 38 ms 236112 KB Output is correct
5 Correct 44 ms 236112 KB Output is correct
6 Correct 38 ms 236200 KB Output is correct
7 Correct 39 ms 236124 KB Output is correct
8 Correct 98 ms 285268 KB Output is correct
9 Correct 106 ms 287224 KB Output is correct
10 Correct 115 ms 287408 KB Output is correct
11 Correct 106 ms 285780 KB Output is correct
12 Correct 133 ms 298068 KB Output is correct
13 Correct 158 ms 298904 KB Output is correct
14 Correct 82 ms 245120 KB Output is correct
15 Correct 126 ms 279124 KB Output is correct
16 Correct 102 ms 275536 KB Output is correct
17 Correct 95 ms 272332 KB Output is correct
18 Correct 57 ms 238520 KB Output is correct
19 Correct 57 ms 238148 KB Output is correct
20 Correct 59 ms 238420 KB Output is correct
21 Correct 57 ms 238028 KB Output is correct
22 Correct 53 ms 238324 KB Output is correct
23 Correct 64 ms 238904 KB Output is correct
24 Correct 125 ms 282888 KB Output is correct
25 Correct 120 ms 284568 KB Output is correct
26 Correct 107 ms 282096 KB Output is correct
27 Correct 111 ms 282788 KB Output is correct
28 Correct 123 ms 256504 KB Output is correct
29 Correct 89 ms 244568 KB Output is correct