oj.uz

Submission #839458

# Submission time Handle Problem Language Result Execution time Memory
839458 2023-08-30T05:27:44 Z huutuan Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 799140 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, const vector<int> &a){
      if (l==r){
         t[k]=ST_node(a[l-1]);
         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, const vector<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];

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;
   st.init(n);
   for (int i=1; i<=n; ++i) st.update(pref[i], suff[i]);
   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 if (n<=5000) 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 4 ms 9812 KB Output is correct
2 Correct 4 ms 9752 KB Output is correct
3 Correct 4 ms 9812 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 5 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 545 ms 537636 KB Output is correct
2 Correct 619 ms 537204 KB Output is correct
3 Correct 673 ms 537232 KB Output is correct
4 Correct 637 ms 537256 KB Output is correct
5 Correct 971 ms 799068 KB Output is correct
6 Correct 996 ms 799140 KB Output is correct
7 Correct 47 ms 16896 KB Output is correct
8 Correct 626 ms 407236 KB Output is correct
9 Correct 574 ms 408416 KB Output is correct
10 Correct 564 ms 408392 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9812 KB Output is correct
2 Correct 4 ms 9752 KB Output is correct
3 Correct 4 ms 9812 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 5 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 545 ms 537636 KB Output is correct
9 Correct 619 ms 537204 KB Output is correct
10 Correct 673 ms 537232 KB Output is correct
11 Correct 637 ms 537256 KB Output is correct
12 Correct 971 ms 799068 KB Output is correct
13 Correct 996 ms 799140 KB Output is correct
14 Correct 47 ms 16896 KB Output is correct
15 Correct 626 ms 407236 KB Output is correct
16 Correct 574 ms 408416 KB Output is correct
17 Correct 564 ms 408392 KB Output is correct
18 Execution timed out 1555 ms 23512 KB Time limit exceeded
19 Halted 0 ms 0 KB -