oj.uz

Submission #488506

# Submission time Handle Problem Language Result Execution time Memory
488506 2021-11-19T11:03:07 Z lukameladze Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 626 ms 805572 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
#define piii pair <int,  pii > 
using namespace std;
const int N = 2e6 + 5;
int in[4*N],out[4*N],tin,cnt[3],endd[4*N],cur,trie[2][4*N][4],le[4*N],ri[4*N],n,m,lst,curi;
string s[N],pref,suf;
int tree[4*N];
vector < piii > queries;
map <int,int> pas[4*N];
vector <pii> que;
vector <int> v[4*N];
void update(int idx, int val) {
	for (int i = idx; i < N; i += i&(-i)) {
		tree[i] += val;
	}
}
int getans(int idx) {
	int pas = 0;
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree[i];
	} return pas;
}
void dfs(int a, int p) {
     tin++;
     in[a] = tin;
     for (int i = 0; i < v[a].size(); i++) {
          if (v[a][i] == p) continue;
          dfs(v[a][i],a);
     }
     out[a] = tin;
     //cout<<a<<" "<<in[a]<<" "<<out[a]<<" \n";
}
void insert(string s, int idx, int ty) {
     int cur = 1;
     for (int i = 0; i < s.size(); i++) {
          if (trie[ty][cur][s[i]-'a'] == 0) {
               cnt[ty]++;
               if (ty == 1) { v[cur].pb(cnt[ty]); }
               trie[ty][cur][s[i] - 'a'] = cnt[ty];
          }
          cur = trie[ty][cur][s[i] - 'a'];
         // cout<<idx<<" "<<ty<<" "<<s[i]<<" "<<cur<<endl;
          if (ty == 0) {
               le[cur] = min(le[cur],idx);
               ri[cur] = max(ri[cur],idx);
          }
     }
     if (ty == 1) {
          endd[idx] = cur;
     }
}
pii find(string s1) {
     int cur = 1;
     for (int i = 0; i < s1.size(); i++) {
          if (!trie[0][cur][s1[i] - 'a']) return{-1,-1};
          cur = trie[0][cur][s1[i] - 'a'];
     }
     return {le[cur],ri[cur]};
}
int find1(string s1) {
     int cur = 1;
     for (int i = 0; i < s1.size(); i++) {
          if (!trie[1][cur][s1[i] - 'a']) return -1;
          cur = trie[1][cur][s1[i] - 'a'];
     }
     return cur;
}
string get(string ss) {
     for (int i = 0; i < ss.size(); i++) {
          if (ss[i] == 'A') ss[i] = 'a';
          if (ss[i] == 'C') ss[i]= 'b';
          if (ss[i] == 'G') ss[i] = 'c';
          if (ss[i] == 'U') ss[i] = 'd';
     }
     return ss;
}
main() {
     std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     cin>>n>>m;
     for (int i = 1; i <= n; i++) {
          cin>>s[i];
          s[i] = get(s[i]);
     }
     for (int i = 1; i < 4*N; i++) le[i] = 1e9, ri[i] = 0;
     le[1] = 1; ri[1] = n;
     sort(s + 1, s + n + 1);
     cnt[0] = cnt[1] = 1;
     for (int i = 1; i <= n; i++) {
          insert(s[i], i,0);
          reverse(s[i].begin(),s[i].end());
          insert(s[i],i,1);
     }
     dfs(1,0);
     
     for (int i = 1; i <= m; i++) {
          cin>>pref>>suf;
          pref = get(pref); suf = get(suf);
          pii x = find(pref);
     //     cout<<x.f<<" "<<x.s<<endl;
     if (x.f == -1) {
          lst = -1;
     } else {
          reverse(suf.begin(), suf.end());
          lst = find1(suf);
         // cout<<lst<<endl;
     }
          queries.pb({lst,{x.f, x.s}});
          que.pb({x.s,lst});
          que.pb({x.f - 1, lst});
       //   cout<<"gam"<<endl;
     } 
     sort(que.begin(),que.end());
     for (int i = 0; i < que.size(); i++) {
          while(curi < que[i].f) {
               curi++;
             //  cout<<in[endd[curi]]<<endl;
               update(in[endd[curi]],1);
          }
          //idd = end[que[i].s];
          if (que[i].s == -1) continue;
          pas[que[i].s][que[i].f] = getans(out[que[i].s]) - getans(in[que[i].s] - 1);
     }
     int vert,lee,rii;
     for (int i = 0; i < queries.size(); i++) {
          vert = queries[i].f;
          lee = queries[i].s.f; rii = queries[i].s.s;
          if (vert == -1) cout<<0<<endl;
          else
          cout<<pas[vert][rii] - pas[vert][lee - 1]<<endl;
     }
}

Compilation message

selling_rna.cpp: In function 'void dfs(int, int)':
selling_rna.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |      for (int i = 0; i < v[a].size(); i++) {
      |                      ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void insert(std::string, int, int)':
selling_rna.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |      for (int i = 0; i < s.size(); i++) {
      |                      ~~^~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> find(std::string)':
selling_rna.cpp:58:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |      for (int i = 0; i < s1.size(); i++) {
      |                      ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int find1(std::string)':
selling_rna.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |      for (int i = 0; i < s1.size(); i++) {
      |                      ~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::string get(std::string)':
selling_rna.cpp:73:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |      for (int i = 0; i < ss.size(); i++) {
      |                      ~~^~~~~~~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main() {
      | ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:117:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |      for (int i = 0; i < que.size(); i++) {
      |                      ~~^~~~~~~~~~~~
selling_rna.cpp:128:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |      for (int i = 0; i < queries.size(); i++) {
      |                      ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 689220 KB Output is correct
2 Correct 312 ms 689128 KB Output is correct
3 Correct 314 ms 689208 KB Output is correct
4 Correct 305 ms 689220 KB Output is correct
5 Correct 352 ms 689220 KB Output is correct
6 Correct 308 ms 689160 KB Output is correct
7 Correct 358 ms 689320 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 805572 KB Output is correct
2 Correct 536 ms 800916 KB Output is correct
3 Correct 408 ms 722608 KB Output is correct
4 Correct 412 ms 721128 KB Output is correct
5 Correct 479 ms 781408 KB Output is correct
6 Correct 509 ms 782728 KB Output is correct
7 Correct 387 ms 691500 KB Output is correct
8 Correct 466 ms 744616 KB Output is correct
9 Correct 455 ms 736400 KB Output is correct
10 Correct 458 ms 734436 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 691272 KB Output is correct
2 Correct 388 ms 690692 KB Output is correct
3 Correct 399 ms 691072 KB Output is correct
4 Correct 377 ms 690940 KB Output is correct
5 Correct 378 ms 690440 KB Output is correct
6 Correct 392 ms 690896 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 689220 KB Output is correct
2 Correct 312 ms 689128 KB Output is correct
3 Correct 314 ms 689208 KB Output is correct
4 Correct 305 ms 689220 KB Output is correct
5 Correct 352 ms 689220 KB Output is correct
6 Correct 308 ms 689160 KB Output is correct
7 Correct 358 ms 689320 KB Output is correct
8 Correct 527 ms 805572 KB Output is correct
9 Correct 536 ms 800916 KB Output is correct
10 Correct 408 ms 722608 KB Output is correct
11 Correct 412 ms 721128 KB Output is correct
12 Correct 479 ms 781408 KB Output is correct
13 Correct 509 ms 782728 KB Output is correct
14 Correct 387 ms 691500 KB Output is correct
15 Correct 466 ms 744616 KB Output is correct
16 Correct 455 ms 736400 KB Output is correct
17 Correct 458 ms 734436 KB Output is correct
18 Correct 435 ms 691272 KB Output is correct
19 Correct 388 ms 690692 KB Output is correct
20 Correct 399 ms 691072 KB Output is correct
21 Correct 377 ms 690940 KB Output is correct
22 Correct 378 ms 690440 KB Output is correct
23 Correct 392 ms 690896 KB Output is correct
24 Correct 547 ms 787768 KB Output is correct
25 Correct 571 ms 788492 KB Output is correct
26 Correct 526 ms 786140 KB Output is correct
27 Correct 431 ms 718868 KB Output is correct
28 Correct 626 ms 708708 KB Output is correct
29 Correct 525 ms 693936 KB Output is correct