oj.uz

Submission #548594

# Submission time Handle Problem Language Result Execution time Memory
548594 2022-04-13T21:53:38 Z NAHDI Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 216 ms 319196 KB 
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using vss = vector<vs>;
using vb = vector<bool>;
using vbb  = vector<vb>;
using ii = pair<int, int>;
using vpi = vector<ii>;
using vpii = vector<vpi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using table = unordered_map<unsigned long, int>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vpll = vector<vpl>;

#define f first
#define s second

#define forn(i, n) for(int i = 0; i < n; i++)
#define fore(i, a, b) for(int i = a; i <= b; i++)
#define for1n(i, n) for(int i = 1; i <= n; i++)
#define rof(i, n) for(int i = n-1; i >= 0; i--)
#define rofe(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define dsc(type) greater<type>

#define Flag cout << "Reached here.\n"
#define FASTIO ios::sync_with_stdio(0); cin.tie(0);

#define pb push_back
#define pbb pop_back
#define sz size
#define rsz resize
#define rsv reserve
#define ins insert

#define lb(a, val) lower_bound(all(a), val);
#define ub(a, val) upper_bound(all(a), val);

#define onec(x) __builtin_popcount(x)
#define end0(x) __builtin_clz(x)
#define beg0(x) __builtin_ctz(x)

#define MAX 1000000000
#define MIN -MAX

#define mod 1000000007LL

#define clr(x, y) memset(x, y, sizeof(x))

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};

ll binpow(ll a, ll b) {
    a %= mod;
    ll res = 1;
    while (b > 0) {
        if (b & 1) res *= a, res %= mod;
        a *= a, a %= mod;
        b >>= 1;
    }
    return res;
}

vi fct(ll n) {
    vi fac;
    while(n%2 == 0) n /= 2, fac.pb(2);
    for(int i = 3; i * i <= n; i += 2) 
        while(n%i == 0) fac.pb(i), n /= i;
    if(n > 1) fac.pb(n);
    return fac;
}

ll gcd(ll a, ll b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return (a*b) / gcd(a, b);
}

#define maxN 100001
#define maxSM 2000002

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

vi Rng[maxSM][4];
int T[maxSM][4];
pair<int, int> rng[maxSM][4];
int t[maxSM][4];

class trie1 {
int sz;

public:
trie1() {
    forn(i, maxSM) forn(j, 4) rng[i][j] = {-1,-1}, t[i][j] = -1;
    sz = 1;
}
void ins(string& s, int ind) {
    int v = 0;
    forn(i, s.sz()) {
        int c = getc(s[i]);
        if(t[v][c] == -1) t[v][c] = sz++, rng[v][c] = {ind, ind-1};
        rng[v][c].s++;
        v = t[v][c];
    }
}
pair<int, int> q(string& s) {
    int v = 0; 
    forn(i, s.sz()) {
        int c = getc(s[i]);
        if(t[v][c] == -1) return {-1, -1};
        if(i == s.sz()-1) return rng[v][c];
        v = t[v][c];
    }
    //Not reachable
    return {-1, -1};
}
};

class trie2 {
int sz;

public:
trie2() {
    forn(i, maxSM)  forn(j, 4) Rng[i][j] = vi{}, T[i][j] = -1;
    sz = 1;
}

void ins(string& s, int ind) {
    int v = 0;
    forn(i, s.sz()) {
        int c = getc(s[i]);
        if(T[v][c] == -1) T[v][c] = sz++;
        Rng[v][c].pb(ind);
        v = T[v][c];
    }
}

int q(string& s, ii& q) {
    if(q.f == -1 && q.s == -1) return 0;
    int v = 0;
    forn(i, s.sz()) {
        int c = getc(s[i]);
        if(T[v][c] == -1) return 0;
        if(i == s.sz()-1) return upper_bound(all(Rng[v][c]), q.s) - lower_bound(all(Rng[v][c]), q.f);
        v = T[v][c];
    }
}
void srt() {
    forn(i, maxSM) forn(j, 4) if(Rng[i][j].sz()) sort(all(Rng[i][j]));
}
};

void task3(int n, int m, vs& s, vs& p, vs& q) {
    sort(all(s));
    trie1 t1;
    trie2 t2;

    forn(i, n) {
        t1.ins(s[i], i);
        reverse(all(s[i]));
        t2.ins(s[i], i);
    }
    t2.srt();
    
    forn(i, m) {
        auto one = t1.q(p[i]);
        auto two = t2.q(q[i], one);
        cout << two << '\n';
    }
}

using si = pair<string, int>; 
void task12(int n, int m, vs& s, vs& p, vs& q) {
    sort(all(s));
    vector<si> rev(n);
    forn(i, n) {
        rev[i].f = s[i], rev[i].s = i;
        reverse(all(rev[i].f));
    }
    sort(all(rev));

    vi t(n+2, -1);
    forn(i, m) {
        int cnt = 0;
        int l1 = lower_bound(all(s), p[i]) - s.begin();
        p[i].back()++;
        int r1 = lower_bound(all(s), p[i]) - s.begin();
        int l2 = lower_bound(all(rev), si{q[i], -1}) - rev.begin();
        q[i].back()++;
        int r2 = lower_bound(all(rev), si{q[i], -1}) - rev.begin();

        for(int j = l1; j < r1; j++) t[j] = i;
        for(int j = l2; j < r2; j++) if(t[rev[j].s] == i) cnt++;
        cout << cnt << '\n';
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    vs s(n);
    forn(i, n) cin >> s[i];
    vs p(m), q(m);
    forn(i, m) {
        cin >> p[i] >> q[i];
        reverse(all(q[i]));
    }
    
    if(n <= 5000 && m <= 5000) {
        task12(n, m, s, p, q);
        return;
    }
    
    int sm = 0;
    forn(i, n) sm += s[i].sz();
    if(sm <= 100005) {
        task3(n, m, s, p, q);
        return;
    }
}

int main() {
    FASTIO;
    solve();
}

Compilation message

selling_rna.cpp: In member function 'void trie1::insert(std::string&, int)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
  116 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:116:5: note: in expansion of macro 'forn'
  116 |     forn(i, s.sz()) {
      |     ^~~~
selling_rna.cpp: In member function 'std::pair<int, int> trie1::q(std::string&)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
  125 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:125:5: note: in expansion of macro 'forn'
  125 |     forn(i, s.sz()) {
      |     ^~~~
selling_rna.cpp:128:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         if(i == s.sz()-1) return rng[v][c];
      |            ~~^~~~~~~~~~~
selling_rna.cpp: In member function 'void trie2::insert(std::string&, int)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
  147 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:147:5: note: in expansion of macro 'forn'
  147 |     forn(i, s.sz()) {
      |     ^~~~
selling_rna.cpp: In member function 'int trie2::q(std::string&, ii&)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
  158 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:158:5: note: in expansion of macro 'forn'
  158 |     forn(i, s.sz()) {
      |     ^~~~
selling_rna.cpp:161:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         if(i == s.sz()-1) return upper_bound(all(Rng[v][c]), q.s) - lower_bound(all(Rng[v][c]), q.f);
      |            ~~^~~~~~~~~~~
selling_rna.cpp:164:1: warning: control reaches end of non-void function [-Wreturn-type]
  164 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 188108 KB Output is correct
2 Correct 89 ms 188124 KB Output is correct
3 Correct 85 ms 188060 KB Output is correct
4 Correct 86 ms 188212 KB Output is correct
5 Correct 90 ms 188176 KB Output is correct
6 Correct 93 ms 188132 KB Output is correct
7 Correct 85 ms 188184 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 194816 KB Output is correct
2 Correct 134 ms 195632 KB Output is correct
3 Correct 132 ms 195276 KB Output is correct
4 Correct 131 ms 195356 KB Output is correct
5 Correct 104 ms 193176 KB Output is correct
6 Correct 106 ms 193332 KB Output is correct
7 Correct 129 ms 196264 KB Output is correct
8 Correct 121 ms 197416 KB Output is correct
9 Correct 110 ms 197452 KB Output is correct
10 Correct 133 ms 194996 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 319196 KB Output is correct
2 Correct 189 ms 317000 KB Output is correct
3 Correct 201 ms 317916 KB Output is correct
4 Correct 215 ms 317316 KB Output is correct
5 Correct 193 ms 316932 KB Output is correct
6 Correct 216 ms 317876 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 188108 KB Output is correct
2 Correct 89 ms 188124 KB Output is correct
3 Correct 85 ms 188060 KB Output is correct
4 Correct 86 ms 188212 KB Output is correct
5 Correct 90 ms 188176 KB Output is correct
6 Correct 93 ms 188132 KB Output is correct
7 Correct 85 ms 188184 KB Output is correct
8 Correct 102 ms 194816 KB Output is correct
9 Correct 134 ms 195632 KB Output is correct
10 Correct 132 ms 195276 KB Output is correct
11 Correct 131 ms 195356 KB Output is correct
12 Correct 104 ms 193176 KB Output is correct
13 Correct 106 ms 193332 KB Output is correct
14 Correct 129 ms 196264 KB Output is correct
15 Correct 121 ms 197416 KB Output is correct
16 Correct 110 ms 197452 KB Output is correct
17 Correct 133 ms 194996 KB Output is correct
18 Correct 207 ms 319196 KB Output is correct
19 Correct 189 ms 317000 KB Output is correct
20 Correct 201 ms 317916 KB Output is correct
21 Correct 215 ms 317316 KB Output is correct
22 Correct 193 ms 316932 KB Output is correct
23 Correct 216 ms 317876 KB Output is correct
24 Incorrect 102 ms 194116 KB Output isn't correct
25 Halted 0 ms 0 KB -