Submission #839460

#	Time	Username	Problem	Language	Result	Execution time	Memory
839460		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	848 ms	799160 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40