oj.uz

Submission #839466

# Submission time Handle Problem Language Result Execution time Memory
839466 2023-08-30T05:39:28 Z Tuanlinh123 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 307 ms 267172 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94284 KB Output is correct
2 Correct 41 ms 94284 KB Output is correct
3 Correct 42 ms 94292 KB Output is correct
4 Correct 41 ms 94284 KB Output is correct
5 Correct 49 ms 94292 KB Output is correct
6 Correct 42 ms 94268 KB Output is correct
7 Correct 41 ms 94292 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 218436 KB Output is correct
2 Correct 205 ms 212336 KB Output is correct
3 Correct 221 ms 217016 KB Output is correct
4 Correct 210 ms 211216 KB Output is correct
5 Correct 307 ms 267172 KB Output is correct
6 Correct 304 ms 266944 KB Output is correct
7 Correct 79 ms 95632 KB Output is correct
8 Correct 208 ms 181080 KB Output is correct
9 Correct 184 ms 181416 KB Output is correct
10 Correct 162 ms 181416 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 103860 KB Output is correct
2 Correct 59 ms 101308 KB Output is correct
3 Correct 64 ms 102072 KB Output is correct
4 Correct 56 ms 100404 KB Output is correct
5 Correct 82 ms 100744 KB Output is correct
6 Correct 62 ms 102196 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94284 KB Output is correct
2 Correct 41 ms 94284 KB Output is correct
3 Correct 42 ms 94292 KB Output is correct
4 Correct 41 ms 94284 KB Output is correct
5 Correct 49 ms 94292 KB Output is correct
6 Correct 42 ms 94268 KB Output is correct
7 Correct 41 ms 94292 KB Output is correct
8 Correct 256 ms 218436 KB Output is correct
9 Correct 205 ms 212336 KB Output is correct
10 Correct 221 ms 217016 KB Output is correct
11 Correct 210 ms 211216 KB Output is correct
12 Correct 307 ms 267172 KB Output is correct
13 Correct 304 ms 266944 KB Output is correct
14 Correct 79 ms 95632 KB Output is correct
15 Correct 208 ms 181080 KB Output is correct
16 Correct 184 ms 181416 KB Output is correct
17 Correct 162 ms 181416 KB Output is correct
18 Correct 61 ms 103860 KB Output is correct
19 Correct 59 ms 101308 KB Output is correct
20 Correct 64 ms 102072 KB Output is correct
21 Correct 56 ms 100404 KB Output is correct
22 Correct 82 ms 100744 KB Output is correct
23 Correct 62 ms 102196 KB Output is correct
24 Correct 232 ms 209868 KB Output is correct
25 Correct 237 ms 209776 KB Output is correct
26 Correct 200 ms 209912 KB Output is correct
27 Correct 214 ms 210108 KB Output is correct
28 Correct 158 ms 129252 KB Output is correct
29 Correct 98 ms 113652 KB Output is correct