oj.uz

Submission #839459

# Submission time Handle Problem Language Result Execution time Memory
839459 2023-08-30T05:29:20 Z huutuan Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 842 ms 799244 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

struct ST_node{
   vector<int> v;
   ST_node (){}
   ST_node (int a): v(1, a){}
   friend ST_node sus(const ST_node& a, const ST_node& b){
      ST_node c; int i, j;
      for (i=0, j=0; i<sz(a.v) && j<sz(b.v); ){
         if (a.v[i]<b.v[j]) c.v.push_back(a.v[i++]);
         else c.v.push_back(b.v[j++]);
      }
      for (; i<sz(a.v); ++i) c.v.push_back(a.v[i]);
      for (; j<sz(b.v); ++j) c.v.push_back(b.v[j]);
      return c;
   }
};

struct SegmentTree{
   int n; vector<ST_node> t;

   void init(int _n){
      n=_n;
      t.assign(4*n+1, ST_node());
   }

   void build(int k, int l, int r, int *a){
      if (l==r){
         t[k]=ST_node(a[l]);
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k]=sus(t[k<<1], t[k<<1|1]);
   }

   void init(int _n, int *a){
      init(_n);
      build(1, 1, n, a);
   }

   void update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k]=ST_node(val);
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k]=sus(t[k<<1], t[k<<1|1]);
   }

   int get(int k, int l, int r, int L, int R, int vl, int vr){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return upper_bound(all(t[k].v), vr)-lower_bound(all(t[k].v), vl);
      int mid=(l+r)>>1;
      return get(k<<1, l, mid, L, R, vl, vr)+get(k<<1|1, mid+1, r, L, R, vl, vr);
   }

   void update(int pos, int val){
      update(1, 1, n, pos, val);
   }

   int get(int l, int r, int vl, int vr){
      return get(1, 1, n, l, r, vl, vr);
   }
} st;

const int A=26, inf=1e9;

struct Node{
   vector<int> idx;
   int nxt[A], min_idx, max_idx, cnt;
   Node (){
      memset(nxt, -1, sizeof nxt);
      min_idx=inf;
      max_idx=-inf;
      cnt=0;
   }
};

struct Trie{
   vector<Node> t;
   vector<int> a;
   Trie (){
      t.emplace_back();
   }
   void insert(const string &s, int idx){
      int cur=0;
      for (char cc:s){
         int c=cc-'A';
         if (t[cur].nxt[c]==-1){
            t[cur].nxt[c]=sz(t);
            t.emplace_back();
         }
         cur=t[cur].nxt[c];
      }
      t[cur].idx.push_back(idx);
   }
   void dfs(int u, int cur){
      for (int i:t[u].idx) a.push_back(i);
      t[u].cnt=sz(t[u].idx);
      t[u].min_idx=cur;
      cur+=sz(t[u].idx);
      for (int i=0; i<A; ++i) if (t[u].nxt[i]!=-1){
         dfs(t[u].nxt[i], cur);
         cur+=t[t[u].nxt[i]].cnt;
         t[u].cnt+=t[t[u].nxt[i]].cnt;
      }
      t[u].max_idx=cur-1;
   }
   pair<int, int> get_range(const string& s){
      int cur=0;
      for (char cc:s){
         int c=cc-'A';
         if (t[cur].nxt[c]==-1) return {-1, -1};
         cur=t[cur].nxt[c];
      }
      return {t[cur].min_idx, t[cur].max_idx};
   }
} pf, sf;

const int N=1e5+1;
int n, m;
string s[N], p[N], q[N];
int pref[N], suff[N], val[N];

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   cin >> n >> m;
   for (int i=1; i<=n; ++i){
      cin >> s[i];
      pf.insert(s[i], i);
      reverse(all(s[i]));
      sf.insert(s[i], i);
      reverse(all(s[i]));
   }
   pf.dfs(0, 1); sf.dfs(0, 1);
   for (int i=0; i<n; ++i) pref[pf.a[i]]=i+1;
   for (int i=0; i<n; ++i) suff[sf.a[i]]=i+1;
   for (int i=1; i<=n; ++i) val[pref[i]]=suff[i];
   st.init(n, val);
   for (int i=1; i<=m; ++i){
      cin >> p[i] >> q[i];
      auto p1=pf.get_range(p[i]);
      reverse(all(q[i]));
      auto p2=sf.get_range(q[i]);
      if (p1.first==-1 || p2.first==-1) cout << "0\n";
      else cout << st.get(p1.first, p1.second, p2.first, p2.second) << '\n';
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 537600 KB Output is correct
2 Correct 503 ms 537188 KB Output is correct
3 Correct 530 ms 537300 KB Output is correct
4 Correct 529 ms 537180 KB Output is correct
5 Correct 842 ms 799088 KB Output is correct
6 Correct 841 ms 799244 KB Output is correct
7 Correct 39 ms 16908 KB Output is correct
8 Correct 522 ms 407292 KB Output is correct
9 Correct 484 ms 408244 KB Output is correct
10 Correct 446 ms 408432 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 27976 KB Output is correct
2 Correct 41 ms 21128 KB Output is correct
3 Correct 48 ms 25780 KB Output is correct
4 Correct 33 ms 22352 KB Output is correct
5 Correct 36 ms 21116 KB Output is correct
6 Correct 44 ms 25780 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9860 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 4 ms 9812 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 4 ms 9812 KB Output is correct
6 Correct 4 ms 9812 KB Output is correct
7 Correct 4 ms 9812 KB Output is correct
8 Correct 520 ms 537600 KB Output is correct
9 Correct 503 ms 537188 KB Output is correct
10 Correct 530 ms 537300 KB Output is correct
11 Correct 529 ms 537180 KB Output is correct
12 Correct 842 ms 799088 KB Output is correct
13 Correct 841 ms 799244 KB Output is correct
14 Correct 39 ms 16908 KB Output is correct
15 Correct 522 ms 407292 KB Output is correct
16 Correct 484 ms 408244 KB Output is correct
17 Correct 446 ms 408432 KB Output is correct
18 Correct 50 ms 27976 KB Output is correct
19 Correct 41 ms 21128 KB Output is correct
20 Correct 48 ms 25780 KB Output is correct
21 Correct 33 ms 22352 KB Output is correct
22 Correct 36 ms 21116 KB Output is correct
23 Correct 44 ms 25780 KB Output is correct
24 Correct 515 ms 538368 KB Output is correct
25 Correct 557 ms 538448 KB Output is correct
26 Correct 501 ms 538340 KB Output is correct
27 Correct 511 ms 538280 KB Output is correct
28 Correct 339 ms 103864 KB Output is correct
29 Correct 112 ms 46844 KB Output is correct