oj.uz

Submission #839457

# Submission time Handle Problem Language Result Execution time Memory
839457 2023-08-30T05:25:55 Z huutuan Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 799180 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 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 5 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 5 ms 9812 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 537708 KB Output is correct
2 Correct 620 ms 537504 KB Output is correct
3 Correct 556 ms 537268 KB Output is correct
4 Correct 621 ms 537224 KB Output is correct
5 Correct 966 ms 799180 KB Output is correct
6 Correct 939 ms 799080 KB Output is correct
7 Correct 47 ms 16900 KB Output is correct
8 Correct 611 ms 407312 KB Output is correct
9 Correct 560 ms 408228 KB Output is correct
10 Correct 543 ms 408360 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
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 5 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 5 ms 9812 KB Output is correct
8 Correct 558 ms 537708 KB Output is correct
9 Correct 620 ms 537504 KB Output is correct
10 Correct 556 ms 537268 KB Output is correct
11 Correct 621 ms 537224 KB Output is correct
12 Correct 966 ms 799180 KB Output is correct
13 Correct 939 ms 799080 KB Output is correct
14 Correct 47 ms 16900 KB Output is correct
15 Correct 611 ms 407312 KB Output is correct
16 Correct 560 ms 408228 KB Output is correct
17 Correct 543 ms 408360 KB Output is correct
18 Execution timed out 1557 ms 23120 KB Time limit exceeded
19 Halted 0 ms 0 KB -