oj.uz

Submission #64546

# Submission time Handle Problem Language Result Execution time Memory
64546 2018-08-04T20:46:08 Z reality Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 824 ms 258348 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 2e6 + 5;
int f[N];
void upd(int i,int h) {
    for (;i <= N;i += i&(-i))
        f[i] += h;
}
int que(int i) {
    int ans = 0;
    for (;i;i -= i&(-i))
        ans += f[i];
    return ans;
}
struct trie {
    trie * t[4];
    int pos;
    trie(void) {
        memset(t,0,sizeof(t));
        pos = -1;
    }
};
typedef trie * tr;
int g(char ch) {
    return ch == 'A' ? 0 : ch == 'U' ? 1 : ch == 'G' ? 2 : 3;
}
void add(tr root,string str) {
    auto cnt = root;
    for (auto it : str) {
        int ch = g(it);
        if (!cnt->t[ch])
            cnt->t[ch] = new trie();
        cnt = cnt->t[ch];
    }
}
void dfs(tr root,int S[],int F[],int &timer) {
    if (!root)
        return;
    root->pos = ++timer;
    S[root->pos] = timer;
    for (int i = 0;i < 4;++i)
        dfs(root->t[i],S,F,timer);
    F[root->pos] = timer;
}
int get(tr root,string str) {
    auto cnt = root;
    for (auto it : str) {
        int ch = g(it);
        cnt = cnt->t[ch];
        if (!cnt)
            break;
    }
    if (!cnt)
        return -1;
    else
        return cnt->pos;
}
tr T[2];
vi up[N];
vector < vi > qu[N];
int S[2][N];
int F[2][N];
int ans[N];
int main(void) {
    T[0] = new trie();
    T[1] = new trie();
    int n,m;
    cin>>n>>m;
    vector < string > s(n);
    for (auto & it : s) {
        cin>>it;
        add(T[0],it);
        reverse(all(it));
        add(T[1],it);
        reverse(all(it));
    }
    int timer = 0;
    dfs(T[0],S[0],F[0],timer);
    timer = 0;
    dfs(T[1],S[1],F[1],timer);
    for (auto it : s) {
        int x = get(T[0],it);
        reverse(all(it));
        int y = get(T[1],it);
        up[S[0][x]].pb(S[1][y]);
    }
    for (int i = 1;i <= m;++i) {
        string a,b;
        cin>>a>>b;
        reverse(all(b));
        int x = get(T[0],a);
        int y = get(T[1],b);
        if (x == -1 || y == -1)
            continue;
        qu[S[0][x] - 1].pb({-1,S[1][y] - 1,F[1][y],i});
        qu[F[0][x]].pb({1,S[1][y] - 1,F[1][y],i});
    }
    for (int i = 1;i < N;++i) {
        for (auto it : up[i])
            upd(it,1);
        for (auto it : qu[i])
            ans[it[3]] += it[0] * (que(it[2]) - que(it[1]));
    }
    for (int i = 1;i <= m;++i)
        cout << ans[i] << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 94424 KB Output is correct
2 Correct 122 ms 94500 KB Output is correct
3 Correct 122 ms 94500 KB Output is correct
4 Correct 118 ms 94500 KB Output is correct
5 Correct 122 ms 94540 KB Output is correct
6 Correct 114 ms 94572 KB Output is correct
7 Correct 119 ms 94572 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 217224 KB Output is correct
2 Correct 710 ms 217224 KB Output is correct
3 Correct 644 ms 217224 KB Output is correct
4 Correct 720 ms 217224 KB Output is correct
5 Correct 718 ms 253848 KB Output is correct
6 Correct 740 ms 258348 KB Output is correct
7 Correct 492 ms 258348 KB Output is correct
8 Correct 790 ms 258348 KB Output is correct
9 Correct 785 ms 258348 KB Output is correct
10 Correct 570 ms 258348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 258348 KB Output is correct
2 Correct 185 ms 258348 KB Output is correct
3 Correct 161 ms 258348 KB Output is correct
4 Correct 204 ms 258348 KB Output is correct
5 Correct 191 ms 258348 KB Output is correct
6 Correct 227 ms 258348 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 94424 KB Output is correct
2 Correct 122 ms 94500 KB Output is correct
3 Correct 122 ms 94500 KB Output is correct
4 Correct 118 ms 94500 KB Output is correct
5 Correct 122 ms 94540 KB Output is correct
6 Correct 114 ms 94572 KB Output is correct
7 Correct 119 ms 94572 KB Output is correct
8 Correct 658 ms 217224 KB Output is correct
9 Correct 710 ms 217224 KB Output is correct
10 Correct 644 ms 217224 KB Output is correct
11 Correct 720 ms 217224 KB Output is correct
12 Correct 718 ms 253848 KB Output is correct
13 Correct 740 ms 258348 KB Output is correct
14 Correct 492 ms 258348 KB Output is correct
15 Correct 790 ms 258348 KB Output is correct
16 Correct 785 ms 258348 KB Output is correct
17 Correct 570 ms 258348 KB Output is correct
18 Correct 241 ms 258348 KB Output is correct
19 Correct 185 ms 258348 KB Output is correct
20 Correct 161 ms 258348 KB Output is correct
21 Correct 204 ms 258348 KB Output is correct
22 Correct 191 ms 258348 KB Output is correct
23 Correct 227 ms 258348 KB Output is correct
24 Correct 696 ms 258348 KB Output is correct
25 Correct 745 ms 258348 KB Output is correct
26 Correct 717 ms 258348 KB Output is correct
27 Correct 731 ms 258348 KB Output is correct
28 Correct 824 ms 258348 KB Output is correct
29 Correct 566 ms 258348 KB Output is correct