oj.uz

Submission #848301

# Submission time Handle Problem Language Result Execution time Memory
848301 2023-09-12T03:20:58 Z quandlm Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 662572 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define pi pair<int,int>
#define ple tuple<int,int,int>
#define fi first
#define se second
#define ii make_pair
#define isz(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define heap_max(a) priority_queue<a>
#define heap_max(a) priority_queue<a,vector<a>,greater<a>>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T>
//using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 10;

int n, q, l, r;
string s[N];

struct Trie {
        struct Node {
               Node* child[30];
               int cnt;
               vector<int>mem;
               Node () {
                     for (int i = 0; i <= 26; ++i) child[i] = nullptr;
                     cnt = 0;
                     mem = {};
               };
        };
        Node* root = new Node();

        void add (string s, int idx) {
             Node* p = root;
             for (int i = 0; i < isz(s); ++i) {
                  int c = (s[i] - 'A');
                  if (p -> child[c] == nullptr) {
                      p -> child[c] = new Node();
                  }
                  p = p -> child[c];
                  p -> mem.push_back(idx);
             }
        }

        void get_prefix (string s) {
             Node* p = root;
             for (int i = 0; i < isz(s); ++i) {
                  int c = (s[i] - 'A');
                  if (p -> child[c] == nullptr) {
                      return;
                  }
                  p = p -> child[c];
             }
             l = p -> mem.front();
             r = p -> mem.back();
             return;
        }

        int get_sufix (string s) {
            Node* p = root;
            for (int i = 0; i < isz(s); ++i) {
                 int c = (s[i] - 'A');
                 if (p -> child[c] == nullptr) {
                      return 0;
                 }
                 p = p -> child[c];
            }
            int left = lower_bound(ALL(p->mem), l)-p->mem.begin();
            int right = upper_bound(ALL(p->mem), r)-p->mem.begin()-1;
            return right - left + 1;
        }
} tree1, tree2;

int pref (string x, string y) {
    if (isz(x) < isz(y)) return 0;
    int mn = isz(y);
    for (int i = 0; i < isz(y); ++i) {
         if (x[i] != y[i]) return 0;
    }
    return 1;
}

int suf (string x, string y) {
    if (isz(x) < isz(y)) return 0;
    int mn = isz(y);
    reverse(ALL(x));
    reverse(ALL(y));
    for (int i = 0; i < isz(y); ++i) {
         if (x[i] != y[i]) return 0;
    }
    return 1;
}

int main () {
      file("dynamic");
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

      cin >> n >> q;
      FOR(i,1,n) cin >> s[i];
      sort(s + 1, s + n + 1);
      for (int i = 1; i <= n; ++i) tree1.add(s[i], i);
      for (int i = 1; i <= n; ++i) {
           string rev = s[i];
           reverse(ALL(rev));
           tree2.add(rev, i);
      }
      while(q--) {
            int res = 0;
            string x, y; cin >> x >> y;
            for (int i = 1; i <= n; ++i) {
                 int cnt = 0;
                 cnt += pref(s[i],x);
                 cnt += suf(s[i],y);
                 res += (cnt == 2) ;
            }
            cout << res << '\n';
//            l = -1; r = -1;
//            tree1.get_prefix(x);
//            if (l == -1) {
//                cout << 0 << '\n';
//                continue;
//            }
//            cout << tree2.get_sufix(y) << '\n';
      }

}

Compilation message

selling_rna.cpp:16: warning: "heap_max" redefined
   16 | #define heap_max(a) priority_queue<a,vector<a>,greater<a>>
      | 
selling_rna.cpp:15: note: this is the location of the previous definition
   15 | #define heap_max(a) priority_queue<a>
      | 
selling_rna.cpp: In function 'int pref(std::string, std::string)':
selling_rna.cpp:87:9: warning: unused variable 'mn' [-Wunused-variable]
   87 |     int mn = isz(y);
      |         ^~
selling_rna.cpp: In function 'int suf(std::string, std::string)':
selling_rna.cpp:96:9: warning: unused variable 'mn' [-Wunused-variable]
   96 |     int mn = isz(y);
      |         ^~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:4:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:106:7: note: in expansion of macro 'file'
  106 |       file("dynamic");
      |       ^~~~
selling_rna.cpp:4:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:106:7: note: in expansion of macro 'file'
  106 |       file("dynamic");
      |       ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31832 KB Output is correct
2 Correct 7 ms 31832 KB Output is correct
3 Correct 8 ms 31832 KB Output is correct
4 Correct 7 ms 31832 KB Output is correct
5 Correct 7 ms 32088 KB Output is correct
6 Correct 7 ms 31832 KB Output is correct
7 Correct 7 ms 31832 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31832 KB Output is correct
2 Correct 7 ms 31832 KB Output is correct
3 Correct 8 ms 31832 KB Output is correct
4 Correct 7 ms 31832 KB Output is correct
5 Correct 7 ms 32088 KB Output is correct
6 Correct 7 ms 31832 KB Output is correct
7 Correct 7 ms 31832 KB Output is correct
8 Execution timed out 1575 ms 662572 KB Time limit exceeded
9 Halted 0 ms 0 KB -