oj.uz

Submission #839460

# Submission time Handle Problem Language Result Execution time Memory
839460 2023-08-30T05:30:01 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 848 ms 799160 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 9812 KB Output is correct
2 Correct 4 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 9832 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 517 ms 537596 KB Output is correct
2 Correct 516 ms 537168 KB Output is correct
3 Correct 520 ms 537228 KB Output is correct
4 Correct 500 ms 537148 KB Output is correct
5 Correct 840 ms 799160 KB Output is correct
6 Correct 848 ms 799092 KB Output is correct
7 Correct 42 ms 16896 KB Output is correct
8 Correct 526 ms 407228 KB Output is correct
9 Correct 484 ms 408180 KB Output is correct
10 Correct 424 ms 408296 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 27776 KB Output is correct
2 Correct 40 ms 21140 KB Output is correct
3 Correct 47 ms 25716 KB Output is correct
4 Correct 31 ms 22352 KB Output is correct
5 Correct 32 ms 21108 KB Output is correct
6 Correct 42 ms 25788 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 4 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 9832 KB Output is correct
7 Correct 4 ms 9812 KB Output is correct
8 Correct 517 ms 537596 KB Output is correct
9 Correct 516 ms 537168 KB Output is correct
10 Correct 520 ms 537228 KB Output is correct
11 Correct 500 ms 537148 KB Output is correct
12 Correct 840 ms 799160 KB Output is correct
13 Correct 848 ms 799092 KB Output is correct
14 Correct 42 ms 16896 KB Output is correct
15 Correct 526 ms 407228 KB Output is correct
16 Correct 484 ms 408180 KB Output is correct
17 Correct 424 ms 408296 KB Output is correct
18 Correct 51 ms 27776 KB Output is correct
19 Correct 40 ms 21140 KB Output is correct
20 Correct 47 ms 25716 KB Output is correct
21 Correct 31 ms 22352 KB Output is correct
22 Correct 32 ms 21108 KB Output is correct
23 Correct 42 ms 25788 KB Output is correct
24 Correct 509 ms 538324 KB Output is correct
25 Correct 546 ms 538316 KB Output is correct
26 Correct 506 ms 538300 KB Output is correct
27 Correct 497 ms 538284 KB Output is correct
28 Correct 325 ms 103928 KB Output is correct
29 Correct 123 ms 46876 KB Output is correct