oj.uz

Submission #548593

# Submission time Handle Problem Language Result Execution time Memory
548593 2022-04-13T21:52:32 Z NAHDI Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 196 ms 319100 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, maxN) 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 89 ms 188152 KB Output is correct
2 Correct 99 ms 188228 KB Output is correct
3 Correct 90 ms 188176 KB Output is correct
4 Correct 100 ms 188148 KB Output is correct
5 Correct 91 ms 188112 KB Output is correct
6 Correct 92 ms 188192 KB Output is correct
7 Correct 92 ms 188108 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 194584 KB Output is correct
2 Correct 125 ms 195196 KB Output is correct
3 Correct 130 ms 194940 KB Output is correct
4 Correct 134 ms 195092 KB Output is correct
5 Correct 108 ms 192948 KB Output is correct
6 Correct 110 ms 192844 KB Output is correct
7 Correct 119 ms 195776 KB Output is correct
8 Correct 116 ms 197088 KB Output is correct
9 Correct 124 ms 197216 KB Output is correct
10 Correct 137 ms 194512 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 319100 KB Output is correct
2 Correct 193 ms 317272 KB Output is correct
3 Correct 194 ms 318308 KB Output is correct
4 Correct 181 ms 317524 KB Output is correct
5 Correct 186 ms 317264 KB Output is correct
6 Correct 190 ms 318256 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 188152 KB Output is correct
2 Correct 99 ms 188228 KB Output is correct
3 Correct 90 ms 188176 KB Output is correct
4 Correct 100 ms 188148 KB Output is correct
5 Correct 91 ms 188112 KB Output is correct
6 Correct 92 ms 188192 KB Output is correct
7 Correct 92 ms 188108 KB Output is correct
8 Correct 106 ms 194584 KB Output is correct
9 Correct 125 ms 195196 KB Output is correct
10 Correct 130 ms 194940 KB Output is correct
11 Correct 134 ms 195092 KB Output is correct
12 Correct 108 ms 192948 KB Output is correct
13 Correct 110 ms 192844 KB Output is correct
14 Correct 119 ms 195776 KB Output is correct
15 Correct 116 ms 197088 KB Output is correct
16 Correct 124 ms 197216 KB Output is correct
17 Correct 137 ms 194512 KB Output is correct
18 Correct 196 ms 319100 KB Output is correct
19 Correct 193 ms 317272 KB Output is correct
20 Correct 194 ms 318308 KB Output is correct
21 Correct 181 ms 317524 KB Output is correct
22 Correct 186 ms 317264 KB Output is correct
23 Correct 190 ms 318256 KB Output is correct
24 Incorrect 105 ms 194400 KB Output isn't correct
25 Halted 0 ms 0 KB -