Submission #839466

#	Time	Username	Problem	Language	Result	Execution time	Memory
839466		Tuanlinh123	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	307 ms	267172 KiB

selling_rna

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

map <char, ll> Map;
ll tin[2][200005], tout[2][200005];
ll k, ans[200005];

struct Node
{
    vector <ll> crr;
    ll child[4];

    Node ()
    {
        fill(begin(child), end(child), -1);
    }
};

struct Trie
{
    ll Time=0;
    vector <Node> t;

    Trie ()
    {
        t.emplace_back();
    }

    void addstring(string s, ll idx)
    {
        ll p=0;
        for (ll i=0; i<s.size(); i++)
        {
            ll c=Map[s[i]];
            if (t[p].child[c]==-1)
            {
                t[p].child[c]=t.size();
                t.emplace_back();
            }
            p=t[p].child[c];
        }
        t[p].crr.pb(idx);
    }

    void setup(ll p, ll num)
    {
        Time++;
        for (ll i:t[p].crr)
            tin[num][i]=Time;
        for (ll i=0; i<4; i++)
            if (t[p].child[i]!=-1)
                setup(t[p].child[i], num);
        for (ll i:t[p].crr)
            tout[num][i]=Time;
        k=max(k, Time);
    }
};

vector <ll> num[2000005];
vector <pair<pll, pll>> event[2000005];

struct BIT
{
    ll n;
    vector <ll> bit;

    BIT (ll n): n(n)
    {
        bit.assign(n+5, 0);
    }

    void update(ll i, ll val)
    {
        for (i; i<=n; i+=i&(-i))
            bit[i]+=val;
    }

    ll query(ll l, ll r)
    {
        ll ans=0; l--;
        for (r; r>0; r-=r&(-r))
            ans+=bit[r];
        for (l; l>0; l-=l&(-l))
            ans-=bit[l];
        return ans;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    Map['A']=0; Map['G']=1; Map['C']=2; Map['U']=3;
    ll n, m; cin >> n >> m;
    Trie A1, A2;
    for (ll i=1; i<=n; i++)
    {
        string s; cin >> s;
        A1.addstring(s, i);
        reverse(s.begin(), s.end());
        A2.addstring(s, i);
    }
    for (ll i=1; i<=m; i++)
    {
        string p, s; cin >> p >> s;
        reverse(s.begin(), s.end());
        A1.addstring(p, i+n);
        A2.addstring(s, i+n);
    }
    A1.setup(0, 0); A2.setup(0, 1);
    for (ll i=1; i<=m; i++)
    {
        event[tin[0][i+n]-1].pb({{tin[1][i+n], tout[1][i+n]}, {i, -1}});
        event[tout[0][i+n]].pb({{tin[1][i+n], tout[1][i+n]}, {i, 1}});
    }
    for (ll i=1; i<=n; i++)
        num[tin[0][i]].pb(tin[1][i]);
    BIT A(k);
    for (ll i=0; i<=k; i++)
    {
        for (ll j:num[i])
            A.update(j, 1);
        for (pair<pll, pll> j:event[i])
        {
            ll l=j.fi.fi, r=j.fi.se, idx=j.se.fi, mul=j.se.se;
            ans[idx]+=A.query(l, r)*mul;
        }
    }
    for (ll i=1; i<=m; i++)
        cout << ans[i] << " ";
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::addstring(std::string, long long int)':
selling_rna.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (ll i=0; i<s.size(); i++)
      |                      ~^~~~~~~~~
selling_rna.cpp: In member function 'void BIT::update(long long int, long long int)':
selling_rna.cpp:81:14: warning: statement has no effect [-Wunused-value]
   81 |         for (i; i<=n; i+=i&(-i))
      |              ^
selling_rna.cpp: In member function 'long long int BIT::query(long long int, long long int)':
selling_rna.cpp:88:14: warning: statement has no effect [-Wunused-value]
   88 |         for (r; r>0; r-=r&(-r))
      |              ^
selling_rna.cpp:90:14: warning: statement has no effect [-Wunused-value]
   90 |         for (l; l>0; l-=l&(-l))
      |              ^

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