Submission #1005832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005832		Ice_man	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	158 ms	298904 KiB

selling_rna

/**
 ____    ____    ____    __________________    ____    ____    ____
||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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40