oj.uz

Submission #548595

# Submission time Handle Problem Language Result Execution time Memory
548595 2022-04-13T21:59:13 Z NAHDI Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 434 ms 376252 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))

#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 task34(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 <= 2000002) {
        task34(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++)
......
   81 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:81:5: note: in expansion of macro 'forn'
   81 |     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++)
......
   90 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:90:5: note: in expansion of macro 'forn'
   90 |     forn(i, s.sz()) {
      |     ^~~~
selling_rna.cpp:93:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         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++)
......
  112 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:112:5: note: in expansion of macro 'forn'
  112 |     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++)
......
  123 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:123:5: note: in expansion of macro 'forn'
  123 |     forn(i, s.sz()) {
      |     ^~~~
selling_rna.cpp:126:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         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:129:1: warning: control reaches end of non-void function [-Wreturn-type]
  129 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 188184 KB Output is correct
2 Correct 90 ms 188076 KB Output is correct
3 Correct 86 ms 188180 KB Output is correct
4 Correct 86 ms 188056 KB Output is correct
5 Correct 88 ms 188140 KB Output is correct
6 Correct 89 ms 188148 KB Output is correct
7 Correct 86 ms 188100 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 194508 KB Output is correct
2 Correct 125 ms 195056 KB Output is correct
3 Correct 145 ms 194860 KB Output is correct
4 Correct 133 ms 195028 KB Output is correct
5 Correct 102 ms 192844 KB Output is correct
6 Correct 113 ms 192792 KB Output is correct
7 Correct 116 ms 195908 KB Output is correct
8 Correct 113 ms 196996 KB Output is correct
9 Correct 115 ms 197056 KB Output is correct
10 Correct 147 ms 194516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 319128 KB Output is correct
2 Correct 187 ms 316960 KB Output is correct
3 Correct 191 ms 317904 KB Output is correct
4 Correct 190 ms 317240 KB Output is correct
5 Correct 193 ms 316876 KB Output is correct
6 Correct 198 ms 317904 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 188184 KB Output is correct
2 Correct 90 ms 188076 KB Output is correct
3 Correct 86 ms 188180 KB Output is correct
4 Correct 86 ms 188056 KB Output is correct
5 Correct 88 ms 188140 KB Output is correct
6 Correct 89 ms 188148 KB Output is correct
7 Correct 86 ms 188100 KB Output is correct
8 Correct 102 ms 194508 KB Output is correct
9 Correct 125 ms 195056 KB Output is correct
10 Correct 145 ms 194860 KB Output is correct
11 Correct 133 ms 195028 KB Output is correct
12 Correct 102 ms 192844 KB Output is correct
13 Correct 113 ms 192792 KB Output is correct
14 Correct 116 ms 195908 KB Output is correct
15 Correct 113 ms 196996 KB Output is correct
16 Correct 115 ms 197056 KB Output is correct
17 Correct 147 ms 194516 KB Output is correct
18 Correct 202 ms 319128 KB Output is correct
19 Correct 187 ms 316960 KB Output is correct
20 Correct 191 ms 317904 KB Output is correct
21 Correct 190 ms 317240 KB Output is correct
22 Correct 193 ms 316876 KB Output is correct
23 Correct 198 ms 317904 KB Output is correct
24 Correct 363 ms 369864 KB Output is correct
25 Correct 434 ms 376252 KB Output is correct
26 Correct 368 ms 372400 KB Output is correct
27 Correct 262 ms 333776 KB Output is correct
28 Correct 354 ms 347768 KB Output is correct
29 Correct 251 ms 331368 KB Output is correct