제출 #986082

#제출 시각아이디문제언어결과실행 시간메모리
986082badontSelling RNA Strands (JOI16_selling_rna)C++17
0 / 100
113 ms146516 KiB
#include <bits/stdc++.h> using namespace std; // clang-format off template <typename T, typename = void> struct is_iterable : false_type {};template <typename T>struct is_iterable< T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value,ostream &>::type operator<<(ostream &cout, T const &v);template <typename A, typename B>ostream &operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")";}template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value, ostream &>::type operator<<(ostream &cout, T const &v) { cout << "["; for (auto it = v.begin(); it != v.end();) {cout << *it; if (++it != v.end()) cout << ", "; } return cout << "]";} #ifdef LOCAL void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define debug(...) "zzz" #endif // clang-format on using ll = long long; using ld = long double; using pii = pair<ll, ll>; #define all(x) x.begin(), x.end() #define mp make_pair #define pb push_back #define f first #define s second constexpr int A = 4; struct node { int tin, tout; array<int, 4> c; node() : tin(0), tout(0), c({-1, -1, -1, -1}) {} }; template <typename T> struct fen { vector<T> tr; ll mxn; fen(ll sz) { mxn = sz; tr.assign(sz + 5, 0); } void upd(ll g, T k) { g++; assert(g != 0); for (; g <= mxn; g += g & -g) tr[g] += k; } T ge(ll g) { g++; T res = 0; for (; g; g -= g & -g) res += tr[g]; return res; } T rng(ll l, ll r) { return ge(r) - ge(l - 1); } }; constexpr int N = 2e6 + 5; node p1[N], p2[N]; void solve() { // open int n, m; cin >> n >> m; vector<vector<int>> a(n); for (auto &u : a) { string s; cin >> s; u.resize(s.size()); for (int i = 0; i < (int)s.size(); i++) { switch (s[i]) { case 'A': u[i] = 0; break; case 'C': u[i] = 1; break; case 'G': u[i] = 2; break; case 'U': u[i] = 3; break; }; } } vector<vector<int>> fo(m), ba(m); for (int i = 0; i < m; i++) { string s; cin >> s; { auto &u = fo[i]; u.resize(s.size()); for (int i = 0; i < (int)s.size(); i++) { switch (s[i]) { case 'A': u[i] = 0; break; case 'C': u[i] = 1; break; case 'G': u[i] = 2; break; case 'U': u[i] = 3; break; }; } } cin >> s; { auto &u = ba[i]; u.resize(s.size()); for (int i = 0; i < (int)s.size(); i++) { switch (s[i]) { case 'A': u[i] = 0; break; case 'C': u[i] = 1; break; case 'G': u[i] = 2; break; case 'U': u[i] = 3; break; }; } reverse(all(u)); } } int pool_1_nxt = 1, pool_2_nxt = 1; for (int i = 0; i < n; i++) { debug(i); const auto &h = a[i]; int cur = 0; for (const auto u : h) { if (p1[cur].c[u] == -1) { p1[cur].c[u] = pool_1_nxt++; } cur = p1[cur].c[u]; } auto hc = h; reverse(all(hc)); cur = 0; for (const auto u : hc) { if (p2[cur].c[u] == -1) { p2[cur].c[u] = pool_2_nxt++; } cur = p2[cur].c[u]; } } int cc = 0; auto dfs = [&](auto &dfs, int g, auto pool) -> void { pool[g].tin = cc++; for (int i = 0; i < 4; i++) { if (pool[g].c[i] != -1) { dfs(dfs, pool[g].c[i], pool); } } pool[g].tout = cc++; }; dfs(dfs, 0, p1); cc = 0; dfs(dfs, 0, p2); vector<array<int, 4>> range_query(m); for (int i = 0; i < m; i++) { auto &[l1, r1, l2, r2] = range_query[i]; int cur = 0; for (auto u : fo[i]) { if (p1[cur].c[u] == -1) { l1 = r1 = -1; break; } cur = p1[cur].c[u]; } if (l1 != -1) { l1 = p1[cur].tin; r1 = p1[cur].tout; } cur = 0; for (auto u : ba[i]) { if (p2[cur].c[u] == -1) { l2 = r2 = -1; break; } cur = p2[cur].c[u]; } if (r1 != -1) { l2 = p2[cur].tin; r2 = p2[cur].tout; } } vector<pii> locations; for (int i = 0; i < n; i++) { int x = -1, y = -1; const auto &h = a[i]; int cur = 0; for (const auto u : h) { cur = p1[cur].c[u]; } x = cur; auto hc = h; cur = 0; reverse(all(hc)); for (const auto u : hc) { cur = p2[cur].c[u]; } y = cur; locations.pb({x, y}); } int max_x = p1[0].tout + 1; vector pt_bin(max_x, vector<int>()); vector add_bin(max_x, vector<array<int, 3>>()); vector sub_bin(max_x, vector<array<int, 3>>()); for (auto [x, y] : locations) { pt_bin[x].pb(y); } for (int i = 0; i < m; i++) { const auto [l1, r1, l2, r2] = range_query[i]; if (l1 != -1 and l2 != -1) { if (l1 > 0) { sub_bin[l1 - 1].pb({l2, r2, i}); } add_bin[r1].pb({l2, r2, i}); } } int max_y = p2[0].tout + 1; fen<ll> tree(max_y); vector<ll> ans(m); for (int x = 0; x < max_x; x++) { for (auto y : pt_bin[x]) { tree.upd(y, 1); } for (auto [l, r, qid] : sub_bin[x]) { ans[qid] -= tree.rng(l, r); } for (auto [l, r, qid] : add_bin[x]) { ans[qid] += tree.rng(l, r); } } for (auto &u : ans) cout << u << '\n'; } int main() { cin.tie(0)->sync_with_stdio(false); ll T = 1; // cin >> T; for (int t = 0; t < T; t++) solve(); cout.flush(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:11:22: warning: statement has no effect [-Wunused-value]
   11 |   #define debug(...) "zzz"
      |                      ^~~~~
selling_rna.cpp:141:5: note: in expansion of macro 'debug'
  141 |     debug(i);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...