oj.uz

Submission #366270

# Submission time Handle Problem Language Result Execution time Memory
366270 2021-02-13T17:59:00 Z ACmachine Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 225 ms 106104 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}
vi a;
struct node{
    array<int, 4> nxt;
    int in, out;
    node(){fill(all(nxt), -1);} 
};
struct Trie{
    vector<node> tree;   
    int t = 0;
    Trie(){tree.pb(node());}
    void insert_string(string s){
        int v = 0;
        REP(i, s.length()){
            if(tree[v].nxt[a[s[i]]] == -1){
                tree[v].nxt[a[s[i]]] = tree.size();
                tree.push_back(node());
            }
            v = tree[v].nxt[a[s[i]]];
        }
    }
    void dfs(int v){
        tree[v].in = t++;
        REP(j, 4){
            if(tree[v].nxt[j] != -1)
                dfs(tree[v].nxt[j]);
        }
        tree[v].out = t;
    }
    pair<int, int> get_range(string s){
        int v = 0;
        REP(i, s.length()){
            if(tree[v].nxt[a[s[i]]] == -1) return mp(-INF, -INF);
            v = tree[v].nxt[a[s[i]]];
        }
        return mp(tree[v].in, tree[v].out);
    }
};

template<typename T> 
struct fenwick{
    vector<T> tree;
    int n;
    fenwick(){}
    fenwick(int _n) {
        n = _n;
        tree.resize(n+1, 0);
    }
    void update(int x, T val){
        ++x; 
        while(x <= n){
            tree[x] += val;
            x += (x & -x); 
        }
    }
    T pref_query(int x){ // query 0 .. x], ++x because BIT is indexed from 1 internally
        ++x;
        T res = 0;
        while(x > 0){
            res += tree[x];
            x -= (x & -x);
        }
        return res;
    }
    T query(int l, int r){ // query [l, r) 
        return pref_query(--r) - pref_query(--l);
    }
};

int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
    a = vector<int>(120); a[(int)'A'] = 0; a[(int)'G'] = 1; a[(int)'C'] = 2; a[(int)'U'] = 3;
	int n, m;
    cin >> n >> m;
    vector<string> rna_chains(n);
    vector<array<int, 2>> points(n);  
    Trie T; Trie T2;
    REP(i, n){
        cin >> rna_chains[i];
        T.insert_string(rna_chains[i]); 
    }
    T.dfs(0);
    REP(i, n){
        points[i][0] = T.get_range(rna_chains[i]).ff;
    }
    REP(i, n){
        reverse(all(rna_chains[i]));
        T2.insert_string(rna_chains[i]);
    }
    T2.dfs(0);
    REP(i, n){
        points[i][1] = T2.get_range(rna_chains[i]).ff;
    }
    struct ev{
        int m;
        int y1; 
        int l, r;
        int id; 
        bool operator<(ev &oth){
            return y1 < oth.y1;
        }
    };
    sort(all(points));
    vector<int> ans(m, 0); 
    vector<ev> events;
    REP(i, m){
        string p, q; cin >> p >> q;
        reverse(all(q));
        pair<int, int> f = T.get_range(p);
        pair<int, int> s = T2.get_range(q);
        if(f == mp(-INF, -INF) || s == mp(-INF, -INF)) continue;
        events.pb({-1, f.ff, s.ff, s.ss, i});
        events.pb({1, f.ss, s.ff, s.ss, i});
    }
    sort(all(events));
    fenwick<int> ft(2000005);
    vector<int> ys;
    REP(i, n) ys.pb(points[i][0]);
    ys.erase(unique(all(ys)), ys.end());
    ys.pb(2 * INF + 17);
    int pp = 0;
    int pp2 = 0;
    for(int yy : ys){
        while(pp < events.size() && events[pp].y1 <= yy){
            ans[events[pp].id] += events[pp].m * ft.query(events[pp].l, events[pp].r);
            pp++;
        } 
        while(pp2 < points.size() && points[pp2][0] <= yy){
            ft.update(points[pp2][1], 1);
            pp2++;
        } 
    }
    REP(i, m) cout << ans[i] << "\n";
    return 0;
}

Compilation message

selling_rna.cpp: In member function 'void Trie::insert_string(std::string)':
selling_rna.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
selling_rna.cpp:28:18: note: in expansion of macro 'FOR'
   28 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
selling_rna.cpp:95:9: note: in expansion of macro 'REP'
   95 |         REP(i, s.length()){
      |         ^~~
selling_rna.cpp: In member function 'std::pair<int, int> Trie::get_range(std::string)':
selling_rna.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
selling_rna.cpp:28:18: note: in expansion of macro 'FOR'
   28 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
selling_rna.cpp:113:9: note: in expansion of macro 'REP'
  113 |         REP(i, s.length()){
      |         ^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:206:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::ev>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |         while(pp < events.size() && events[pp].y1 <= yy){
      |               ~~~^~~~~~~~~~~~~~~
selling_rna.cpp:210:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |         while(pp2 < points.size() && points[pp2][0] <= yy){
      |               ~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 57152 KB Output is correct
2 Correct 163 ms 55156 KB Output is correct
3 Correct 174 ms 57092 KB Output is correct
4 Correct 164 ms 54756 KB Output is correct
5 Correct 225 ms 104460 KB Output is correct
6 Correct 224 ms 106104 KB Output is correct
7 Correct 62 ms 15804 KB Output is correct
8 Correct 162 ms 58700 KB Output is correct
9 Correct 151 ms 55596 KB Output is correct
10 Correct 132 ms 55468 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13280 KB Output is correct
2 Correct 35 ms 11328 KB Output is correct
3 Correct 41 ms 12412 KB Output is correct
4 Correct 35 ms 11732 KB Output is correct
5 Correct 33 ms 11392 KB Output is correct
6 Correct 41 ms 12412 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 8 ms 8172 KB Output is correct
5 Correct 7 ms 8172 KB Output is correct
6 Correct 6 ms 8300 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 170 ms 57152 KB Output is correct
9 Correct 163 ms 55156 KB Output is correct
10 Correct 174 ms 57092 KB Output is correct
11 Correct 164 ms 54756 KB Output is correct
12 Correct 225 ms 104460 KB Output is correct
13 Correct 224 ms 106104 KB Output is correct
14 Correct 62 ms 15804 KB Output is correct
15 Correct 162 ms 58700 KB Output is correct
16 Correct 151 ms 55596 KB Output is correct
17 Correct 132 ms 55468 KB Output is correct
18 Correct 44 ms 13280 KB Output is correct
19 Correct 35 ms 11328 KB Output is correct
20 Correct 41 ms 12412 KB Output is correct
21 Correct 35 ms 11732 KB Output is correct
22 Correct 33 ms 11392 KB Output is correct
23 Correct 41 ms 12412 KB Output is correct
24 Correct 169 ms 54964 KB Output is correct
25 Correct 189 ms 57524 KB Output is correct
26 Correct 159 ms 54664 KB Output is correct
27 Correct 171 ms 54464 KB Output is correct
28 Correct 176 ms 34000 KB Output is correct
29 Correct 110 ms 21100 KB Output is correct