Submission #1295283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295283		HoriaHaivas	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	24 ms	33636 KiB

selling_rna

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct Node
{
    int ends;
    int nxt[4];
};

Node emptyNode= {0,{0,0,0,0}};

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

struct ceva
{
    int lin;
    int delta;
    int poz;
};
struct altceva
{
    int col;
    int delta;
};

const int inf=1e9;
int aib[800005];
int tinp[800005];
int tins[800005];
int toutp[800005];
int touts[800005];
int ans[100005];
vector<altceva> updates[800005];
vector<ceva> queries[800005];

int timer,timer1,timer2;

class Trie
{
public:
    int sz;
    Node trie[800005];
    map<string,int>endies;///asta se putea face mult mai bine dar cred ca intra si asa

    void init()
    {
        sz=0;
        trie[0]=emptyNode;
    }

    void ins(string s, int dir)
    {
        int i,node,c;
        node=0;
        if (dir==1)
        {
            for (i=0; i<s.size(); i++)
            {
                c=val(s[i]);
                if (trie[node].nxt[c]==0)
                {
                    sz++;
                    trie[node].nxt[c]=sz;
                    trie[sz]=emptyNode;
                }
                node=trie[node].nxt[c];
            }
        }
        else
        {
            for (i=s.size()-1;i>=0;i--)
            {
                c=val(s[i]);
                if (trie[node].nxt[c]==0)
                {
                    sz++;
                    trie[node].nxt[c]=sz;
                    trie[sz]=emptyNode;
                }
                node=trie[node].nxt[c];
            }
        }
        trie[node].ends++;
        endies[s]=node;
    }

    pair<int,int> interval(string s, int dir)
    {
        int i,node,c;
        node=0;
        for (i=0; i<s.size(); i++)
        {
            c=val(s[i]);
            if (trie[node].nxt[c]==0)
            {
                return {inf,inf};
            }
            node=trie[node].nxt[c];
        }
        if (dir==0)
            return {tins[node],touts[node]};
        else
            return {tinp[node],toutp[node]};
    }
} triep,tries;

void dfsp(int node)
{
    timer++;
    tinp[node]=timer;
    int i,child;
    for (i=0; i<4; i++)
    {
        child=triep.trie[node].nxt[i];
        if (child!=0)
        {
            dfsp(child);
        }
    }
    toutp[node]=timer;
}

void dfss(int node)
{
    timer++;
    tins[node]=timer;
    int i,child;
    for (i=0; i<4; i++)
    {
        child=tries.trie[node].nxt[i];
        if (child!=0)
        {
            dfss(child);
        }
    }
    touts[node]=timer;
}

void update(int idx, int delta)
{
    while (idx<=timer1)
    {
        aib[idx]+=delta;
        idx+=idx&(-idx);
    }
}

int query(int idx)
{
    int ans;
    ans=0;
    while (idx>0)
    {
        ans+=aib[idx];
        idx-=idx&(-idx);
    }
    return ans;
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,i,j,othernode;
    pair<int,int> res1,res2;
    string s,pref,suff;
    cin >> n >> m;
    triep.init();
    tries.init();
    for (i=1; i<=n; i++)
    {
        cin >> s;
        triep.ins(s,1);
        tries.ins(s,-1);
    }
    timer=0;
    dfss(0);
    timer1=timer;
    timer=0;
    dfsp(0);
    timer2=timer;
    for (i=1; i<=m; i++)
    {
        cin >> pref >> suff;
        reverse(suff.begin(),suff.end());
        res1=triep.interval(pref,1);
        res2=tries.interval(suff,0);
        /*
        debugs(pref);
        debugs(res1.first);
        debug(res1.second);
        debugs(suff);
        debugs(res2.first);
        debug(res2.second);
        */
        if (res1.first==inf && res1.second==inf || res2.first==inf && res2.second==inf)
        {
            ans[i]=0;
        }
        else
        {
            queries[res1.second].push_back({res2.second,1,i});///dreapta jos
            queries[res1.second].push_back({res2.first-1,-1,i});///stanga jos
            queries[res1.first-1].push_back({res2.second,-1,i});///dreapta sus
            queries[res1.first-1].push_back({res2.first-1,1,i});///stanga sus
        }
    }
    for (auto x : triep.endies)
    {
        /*
        debugs(x.first);
        debugs(tinp[x.second]);
        */
        othernode=tries.endies[x.first];
        //debug(tins[othernode]);
        //debug(tries.trie[othernode].ends);
        updates[tinp[x.second]].push_back({tins[othernode],tries.trie[othernode].ends});
    }
    for (i=1; i<=timer2; i++)
    {
        for (auto x : updates[i])
        {
            /*
            debugs(i);
            debug(x);
            */
            update(x.col,x.delta);
        }
        for (auto x : queries[i])
        {
            /*
            debugs(x.poz);
            debugs(i);
            debugs(x.lin);
            debug(query(x.lin));
            */
            ans[x.poz]+=query(x.lin)*x.delta;
        }
    }
    for (i=1; i<=m; i++)
    {
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'long long int val(char)':
selling_rna.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40