Submission #570414

#	Time	Username	Problem	Language	Result	Execution time	Memory
570414		cjoa	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	177 ms	66316 KiB

selling_rna

#include <iostream>

#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <cassert>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::cprint(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif


using VI = vector<int>;
using II = pair<int,int>;


class BinaryIndexedTree {
   int N;
   vector<int> tree;
public:
   BinaryIndexedTree(int _N) : N(_N), tree(_N+1) {}

   int query(int idx) const {
      assert(idx <= N);
      int res = 0;
      for (int i = idx; i > 0; i -= (i & -i))
         res += tree[i];
      return res;
   }

   int query(int L, int R) const {
      R = min(R, N);
      L = max(L, 1);
      return L <= R ? query(R) - query(L-1) : 0;
   }

   void update(int idx, int val = 1) {
      for (int i = idx; i <= N; i += (i & -i))
         tree[i] += val;
   }
};

struct Trie {
   struct TrieNode {
      int child[4];
      TrieNode() {
         memset(child, -1, sizeof(child));
      }
   };

   vector<TrieNode> nodes;

   static const int root = 0;   // root is at index 0

   Trie() {
   // nodes.reserve(8000000);
      nodes.push_back(TrieNode());  // 1st node is root
   }

   int insert(const string& S) {
      int cur = root;
      for (char c : S) {
         int k = c - '0';
         int nxt = nodes[cur].child[k];
         if (nxt < 0) {
            nxt = nodes.size();
            nodes.push_back(TrieNode());
            nodes[cur].child[k] = nxt;
         }
         cur = nxt;
      }
      return cur;
   }

   int dfs_time;
   VI dfs_start, dfs_end;
   void dfs(int cur) {
      dfs_start[cur] = ++dfs_time;
      for (int k = 0; k < 4; ++k) {
         int nxt = nodes[cur].child[k];
         if (nxt < 0) continue;
         dfs(nxt);
      }
      dfs_end[cur] = dfs_time;
   }
   
   void explore() {
      dfs_time  = 0;
      dfs_start = VI(nodes.size());
      dfs_end   = VI(nodes.size());
      dfs(root);
   }

   int find(const string& S) {
      int cur = root;
      for (char c : S) {
         int k = c - '0';
         int nxt = nodes[cur].child[k];
         if (nxt < 0) return -1;
         cur = nxt;
      }
      return cur;
   }
};

const string valid_chars = "ACGU";
void transform(string& S) {
   for (int i = 0; i < (int) S.size(); ++i)
      S[i] = '0' + valid_chars.find( S[i] );
}

struct Rect {
   II tl, br;
};

struct Event {
   int id, x;
   char type;
};

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);

   Trie trie_fwd, trie_rev;

   int N, M;
   cin >> N >> M;

   vector<II> IDs;

   for (int i = 0; i < N; ++i) {
      string chain;
      cin >> chain;
      transform(chain);
      int idx = trie_fwd.insert(chain);
      reverse(chain.begin(), chain.end());
      int idy = trie_rev.insert(chain);
      IDs.emplace_back(idx, idy);
   }
   DEBUG(IDs);

   trie_fwd.explore();
   trie_rev.explore();

   vector<II> points;
   for (II id : IDs) {
      points.emplace_back(
         trie_fwd.dfs_start[id.first],
         trie_rev.dfs_start[id.second]
      );
   }
   for (int i = 0; i < N; ++i)
      DEBUG(i, points[i]);

   vector<Rect> rects;
   for (int j = 0; j < M; ++j) {
      string prefix, suffix;
      cin >> prefix >> suffix;
      transform(prefix);
      transform(suffix);
      reverse(suffix.begin(), suffix.end());

      int idx = trie_fwd.find(prefix);
      int idy = trie_rev.find(suffix);
      if (idx < 0 or idy < 0) {
         rects.push_back({
            II(-1, -1), II(-1, -1)
         });
      }
      else {
         rects.push_back({
            II(trie_fwd.dfs_start[idx], trie_rev.dfs_start[idy]),
            II(trie_fwd.dfs_end[idx], trie_rev.dfs_end[idy])
         });
      }
   }

   for (int j = 0; j < M; ++j)
      DEBUG(j, rects[j].tl, rects[j].br);

   vector<Event> events;
   for (int i = 0; i < N; ++i)
      events.push_back({ i, points[i].first, 'P' });

   for (int j = 0; j < M; ++j) {
      if (rects[j].tl.first < 0) continue;

      events.push_back({ j, rects[j].tl.first, 'L'});
      events.push_back({ j, rects[j].br.first, 'R'});
   }

   sort(events.begin(), events.end(),
      [&] (Event a, Event b) -> bool {
         if (a.x != b.x)
            return a.x < b.x;
         if (a.type != b.type)
            return a.type < b.type;
         return a.id < b.id;
      }
   );

   vector<int> ans(M);
   BinaryIndexedTree bit(trie_rev.dfs_time+1);

   for (Event e : events) {
      DEBUG(e.id, e.type, e.x);
      if (e.type == 'P') {
         int y = points[e.id].second;
         bit.update(y);
      }
      else if (e.type == 'L') {
         int ty = rects[e.id].tl.second;
         int by = rects[e.id].br.second;
         ans[e.id] += -bit.query(ty, by);
      }
      else {
         int ty = rects[e.id].tl.second;
         int by = rects[e.id].br.second;
         ans[e.id] += bit.query(ty, by);
      }
   }

   for (int j = 0; j < M; ++j)
      cout << ans[j] << '\n';

   return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40