oj.uz

Submission #548591

# Submission time Handle Problem Language Result Execution time Memory
548591 2022-04-13T21:29:00 Z NAHDI Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 36976 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 100005

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

class trie1 {
vpii rng;
vii t;
int sz;

public:
trie1() {
    rng = vpii(maxSM, vpi(4, {-1, -1}));
    t = vii(maxSM, vi(4, -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 {
vector<vii> rng;
vii t;
int sz;

public:
trie2() {
    rng = vector<vii>(maxSM, vii(4));
    t = vii(maxSM, vi(4, -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) {
    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(string& s) {
    int v = 0;
    forn(i, s.sz()) {
        int c = getc(s[i]);
        sort(all(rng[v][c]));
        v = t[v][c];
    }
}
};

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);
    }
    forn(i, n) t2.srt(s[i]);
    
    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++)
......
  114 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:114:5: note: in expansion of macro 'forn'
  114 |     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++)
......
  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 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++)
......
  148 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:148:5: note: in expansion of macro 'forn'
  148 |     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: In member function 'void trie2::srt(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++)
......
  167 |     forn(i, s.sz()) {
      |          ~~~~~~~~~                   
selling_rna.cpp:167:5: note: in expansion of macro 'forn'
  167 |     forn(i, s.sz()) {
      |     ^~~~
selling_rna.cpp: In member function 'int trie2::q(std::string&, ii&)':
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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6744 KB Output is correct
2 Correct 38 ms 8552 KB Output is correct
3 Correct 41 ms 11020 KB Output is correct
4 Correct 50 ms 11092 KB Output is correct
5 Correct 18 ms 7400 KB Output is correct
6 Correct 18 ms 7528 KB Output is correct
7 Correct 30 ms 13336 KB Output is correct
8 Correct 35 ms 15120 KB Output is correct
9 Correct 32 ms 15092 KB Output is correct
10 Correct 51 ms 10156 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 36976 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 17 ms 6744 KB Output is correct
9 Correct 38 ms 8552 KB Output is correct
10 Correct 41 ms 11020 KB Output is correct
11 Correct 50 ms 11092 KB Output is correct
12 Correct 18 ms 7400 KB Output is correct
13 Correct 18 ms 7528 KB Output is correct
14 Correct 30 ms 13336 KB Output is correct
15 Correct 35 ms 15120 KB Output is correct
16 Correct 32 ms 15092 KB Output is correct
17 Correct 51 ms 10156 KB Output is correct
18 Execution timed out 1591 ms 36976 KB Time limit exceeded
19 Halted 0 ms 0 KB -