oj.uz

Submission #839619

# Submission time Handle Problem Language Result Execution time Memory
839619 2023-08-30T10:50:02 Z wibulord Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 443 ms 197536 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define db long double
#define fi first
#define se second
#define pb emplace_back

#define vi vector<int>
#define vii vector<pair<int,int>>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pdd pair<db, db>
#define iii pair<int, pair<int, int> >

#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(a) int((a).size())

#define bit(x) bitset<10>((x))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (1 &((x) >> (i)))
#define clz(x) __builtin_clz((x))
#define ctz(x) __builtin_ctz((x))
#define popc(x) __builtin_popcount((x))
#define clzll(x) __builtin_clzll((x))
#define ctzll(x) __builtin_ctzll((x))
#define popcll(x) __builtin_popcountll((x))

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
#define rep(i, a) for (auto i : a)

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

void print(int x) {cerr << x;}
void print(long long x) {cerr << x;}
void print(long double x) {cerr << x;}
void print(double x) {cerr << x;}
void print(unsigned long long x) {cerr << x;}
void print(char x) {cerr << x;}
void print(bool x) {cerr << (x ? "True" : "False");}
void print(string x) {cerr << x;}

template <typename T,typename H>
void print(pair<T,H> a) {cerr << "("; print(a.fi); cerr << ','; print(a.se); cerr << ')';}
template <typename T>
void print(T vec) {int cnt=0; cerr << "{"; rep(x,vec) cerr << (cnt++?",":""), print(x); cerr << '}';}

void show() {}
template <typename Head, typename ...Tail>
void show(Head H, Tail ...T){
    print(H);
    if (sizeof...(T)) cerr << ", ";
    show(T...);
}
#define debug(X...) cerr << "LINE "  << __LINE__ << " - " <<  "[" << #X << "] = [", show(X), cerr << "]\n"

template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}

inline int gcd(int x,int y){while(y){int tmp=y;y=x%y;x=tmp;} return (x);}
inline int lcm(int x,int y){return (int)(x*y)/gcd(x,y);}

void read(){}
template <typename Head, typename ...Tail>
void read(Head &H, Tail &...T)
{
    int sign = 0;
    char c;
    for (c = getchar(); !isdigit(c); c = getchar())
        if (c == '-') sign = 1;
    H = c - '0';
    for (c = getchar(); isdigit(c); c = getchar())
        H = H * 10 + c - '0';
    if (sign) H = -H;
    read(T...);
}

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}

const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int maxN = 2e5 + 1, maxM = 1e2 + 5;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/
string RNA = "AGCU";

int get_val(char c){
    F0R(i, 4) if(c == RNA[i]) return i;
    return -1;
}

char get_char(int c){
    return RNA[c];
}

struct Trie1{
    struct Node{
        int child[4];
        int l, r, exist;
    };

    vector<Node> node;
    int cur;
    Trie1() : cur(0){
        node.resize(cur+1);
        memset(node[cur].child, -1, sizeof(node[cur].child));
        node[cur].l = oo, node[cur].r = -oo, node[cur].exist;
    }

    int new_node(){
        ++cur;
        node.resize(cur+1);
        memset(node[cur].child, -1, sizeof(node[cur].child));
        node[cur].l = oo, node[cur].r = -oo, node[cur].exist;
        return cur;
    }

    void add(string s, int id){
        int pos = 0;
        F0R(i, sz(s)){
            int c = get_val(s[i]);
            if(node[pos].child[c] == -1) node[pos].child[c] = new_node();
            pos = node[pos].child[c];
            ckmin(node[pos].l, id), ckmax(node[pos].r, id);
        }
        node[pos].exist++;
    }

    pii query(string s){
        int pos = 0;
        F0R(i, sz(s)){
            int c = get_val(s[i]);
            if(node[pos].child[c] == -1) return pii(-1, -1);
            pos = node[pos].child[c];
        }
        return pii(node[pos].l, node[pos].r);
    }

    void dfs(int pos, string curr, vector<string>& res){
        FOR(i, 1, node[pos].exist) res.pb(curr);
        F0R(i, 4) if(node[pos].child[i] != -1){
            curr += get_char(i);
            dfs(node[pos].child[i], curr, res);
            curr.pop_back();
        }
    }

    vector<string> sortt(){
        vector<string> res;
        string curr = "";
        dfs(0, curr, res);
        return res;
    }
};


struct Trie2{
    struct Node{
        int child[4];
        vi ids;
    };

    vector<Node> node;
    int cur;
    Trie2() : cur(0){
        node.resize(cur+1);
        node[cur].ids.clear();
        memset(node[cur].child, -1, sizeof(node[cur].child));
    }

    int new_node(){
        ++cur;
        node.resize(cur+1);
        node[cur].ids.clear();
        memset(node[cur].child, -1, sizeof(node[cur].child));
        return cur;
    }

    void add(string s, int id){
        reverse(all(s));
        int pos = 0;
        F0R(i, sz(s)){
            int c = get_val(s[i]);
            if(node[pos].child[c] == -1) node[pos].child[c] = new_node();
            pos = node[pos].child[c];
            node[pos].ids.pb(id);
        }
    }

    int query(string s, pii range){
        reverse(all(s));
        int pos = 0;
        F0R(i, sz(s)){
            int c = get_val(s[i]);
            if(node[pos].child[c] == -1) return 0;
            pos = node[pos].child[c];
        }
        int l = lower_bound(all(node[pos].ids), range.fi) - node[pos].ids.begin();
        int r = upper_bound(all(node[pos].ids), range.se) - node[pos].ids.begin() - 1;
        return r - l + 1;
    }
};

void sol(){
    int n, q; cin >> n >> q;
    vector<string> v;
    F0R(i, n){
        string s; cin >> s;
        v.pb(s);
    }
    Trie1 list;
    for(string s : v) list.add(s, -1);
    v = list.sortt();
    Trie1 trie1;
    Trie2 trie2;
    F0R(i, n){
        trie1.add(v[i], i+1);
        trie2.add(v[i], i+1);
    }

    while(q--){
        string s, t; cin >> s >> t;
        pii range = trie1.query(s);
        if(range.fi == -1) cout << "0\n";
        else cout << trie2.query(t, range) << '\n'; 
    }
}

signed main(){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    fast; int t = 1;
//    cin >> t;
    while(t--) sol();
    clog << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:259:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  259 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:260:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  260 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 142020 KB Output is correct
2 Correct 227 ms 134388 KB Output is correct
3 Correct 443 ms 174824 KB Output is correct
4 Correct 388 ms 165196 KB Output is correct
5 Correct 346 ms 197536 KB Output is correct
6 Correct 341 ms 179700 KB Output is correct
7 Correct 47 ms 12876 KB Output is correct
8 Correct 231 ms 110340 KB Output is correct
9 Correct 209 ms 99204 KB Output is correct
10 Correct 188 ms 124252 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4988 KB Output is correct
2 Correct 14 ms 2768 KB Output is correct
3 Correct 18 ms 4684 KB Output is correct
4 Correct 14 ms 4428 KB Output is correct
5 Correct 15 ms 2896 KB Output is correct
6 Correct 19 ms 4684 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 223 ms 142020 KB Output is correct
9 Correct 227 ms 134388 KB Output is correct
10 Correct 443 ms 174824 KB Output is correct
11 Correct 388 ms 165196 KB Output is correct
12 Correct 346 ms 197536 KB Output is correct
13 Correct 341 ms 179700 KB Output is correct
14 Correct 47 ms 12876 KB Output is correct
15 Correct 231 ms 110340 KB Output is correct
16 Correct 209 ms 99204 KB Output is correct
17 Correct 188 ms 124252 KB Output is correct
18 Correct 29 ms 4988 KB Output is correct
19 Correct 14 ms 2768 KB Output is correct
20 Correct 18 ms 4684 KB Output is correct
21 Correct 14 ms 4428 KB Output is correct
22 Correct 15 ms 2896 KB Output is correct
23 Correct 19 ms 4684 KB Output is correct
24 Correct 214 ms 118580 KB Output is correct
25 Correct 226 ms 118540 KB Output is correct
26 Correct 216 ms 118564 KB Output is correct
27 Correct 303 ms 149528 KB Output is correct
28 Correct 140 ms 29408 KB Output is correct
29 Correct 54 ms 9544 KB Output is correct