Submission #488506

#	Time	Username	Problem	Language	Result	Execution time	Memory
488506		lukameladze	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	626 ms	805572 KiB

selling_rna

# 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 (stderr)

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