Submission #748723

#TimeUsernameProblemLanguageResultExecution timeMemory
748723PixelCatSelling RNA Strands (JOI16_selling_rna)C++14
35 / 100
530 ms895688 KiB
/* code by PixelCat */ /* meow owo */ #include <bits/stdc++.h> // #define int LL //__int128 #define double long double using namespace std; using LL = long long; // using i128 = __int128_t; using ull = unsigned long long; using pii = pair<int, int>; #define For(i, a, b) for (int i = a; i <= b; i++) #define Fors(i, a, b, s) for (int i = a; i <= b; i += s) #define Forr(i, a, b) for (int i = a; i >= b; i--) #define F first #define S second #define eb emplace_back #define all(x) x.begin(), x.end() #define sz(x) ((int)x.size()) #define mkp make_pair #define MOD (int)(998244353) // #define MOD (int)((LL)1'000'000'007) #define INF (int)(4e18) #define EPS (1e-6) namespace PixelCat { #ifdef NYAOWO #include "/home/pixelcat/yodayo/meow/library/debug.hpp" inline void USACO(const string &s) { cerr << "USACO: " << s << "\n"; } #else #define debug(...) inline void timer() {} inline void USACO(const string &s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } #endif inline void NYA() { ios::sync_with_stdio(false); cin.tie(0); } inline int gcd(int a, int b) { return __gcd(a, b); } inline int lcm(int a, int b) { return a / gcd(a, b) * b; } int fpow(int b, int p, const int &mod = MOD) { int ans = 1; for (; p; p >>= 1, b = b * b % mod) if (p & 1) ans = ans * b % mod; return ans; } template <typename T> inline void chmin(T &_a, const T &_b) { if (_b < _a) _a = _b; } template <typename T> inline void chmax(T &_a, const T &_b) { if (_b > _a) _a = _b; } mt19937_64 rng( chrono::steady_clock::now().time_since_epoch().count()); } // namespace PixelCat using namespace PixelCat; const int MAXN = 100010; // N, Q const int MAXS = 2000010; // total # of characters const int MAXCH = 26; // charcters count using nodeid = int; struct Trie { nodeid cur_node, rt; int dfs_time; nodeid nxt[MAXS][MAXCH]; int l[MAXS]; int r[MAXS]; vector<nodeid> end_node; int ord(const char &ch) { switch(ch) { case 'A': return 0; case 'U': return 1; case 'C': return 2; default: return 3; } } nodeid new_node() { cur_node++; return cur_node; } void init() { memset(nxt, 0, sizeof(nxt)); memset(l, 0, sizeof(l)); memset(r, -1, sizeof(r)); cur_node = 0; rt = new_node(); } void insert(const string &s) { int nd = rt; for(const char &ch:s) { nodeid &nnd = nxt[nd][ord(ch)]; if(!nnd) nnd = new_node(); nd = nnd; } end_node.eb(nd); r[nd]++; } void _dfs(int nd) { l[nd] += dfs_time; r[nd] += dfs_time; dfs_time = r[nd] + 1; For(ch, 0, MAXCH - 1) { nodeid nnd = nxt[nd][ch]; if(nnd) { _dfs(nnd); r[nd] = r[nnd]; } } } void build(int* pos) { dfs_time = 1; _dfs(rt); For(i, 0, sz(end_node) - 1) { nodeid nd = end_node[i]; pos[i + 1] = l[nd]; } } pii find(const string &s) { int nd = rt; for(const char &ch:s) { nodeid &nnd = nxt[nd][ord(ch)]; if(!nnd) return pii(-1, -1); nd = nnd; } return pii(l[nd], r[nd]); } } tt, tr; #define LO(x) ((x) & (-(x))) struct BIT { int n; int a[MAXN]; void init(int _n) { n = _n; memset(a, 0, sizeof(a)); } void add(int i, int x) { while(i <= n) { a[i] += x; i += LO(i); } } int ask(int i) { int res = 0; while(i) { res += a[i]; i -= LO(i); } return res; } int ask(int l, int r) { return ask(r) - ask(l - 1); } } bit; struct SweepingLine { struct Event { int x, yl, yr, id; }; vector<Event> ev; int ans[MAXN]; void init() { memset(ans, 0, sizeof(ans)); } void add_pt(int x, int y) { ev.eb((Event){x, y, 0, 0}); } void add_qry(int id, pii x, pii y) { ev.eb((Event){x.F - 1, y.F, y.S, -id}); ev.eb((Event){x.S, y.F, y.S, id}); } int* solve(int n) { sort(all(ev), [&](const Event &ea, const Event &eb) { if(ea.x != eb.x) return ea.x < eb.x; return ea.id == 0; }); reverse(all(ev)); bit.init(n); while(!ev.empty()) { Event e = ev.back(); ev.pop_back(); if(e.id == 0) { bit.add(e.yl, 1); } else if(e.id > 0) { ans[e.id] += bit.ask(e.yl, e.yr); } else { ans[-e.id] -= bit.ask(e.yl, e.yr); } } return ans; } } swp; int posx[MAXN]; int posy[MAXN]; int32_t main() { NYA(); // nyaacho >/////< cerr << (sizeof(tt) * 2 + sizeof(bit) + sizeof(swp) + sizeof(posx) * 2) << "\n"; int n, q; cin >> n >> q; tt.init(); tr.init(); For(i, 1, n) { string s; cin >> s; tt.insert(s); reverse(all(s)); tr.insert(s); } tt.build(posx); tr.build(posy); swp.init(); For(i, 1, n) { swp.add_pt(posx[i], posy[i]); } For(i, 1, q) { string sx, sy; cin >> sx >> sy; pii px = tt.find(sx); reverse(all(sy)); pii py = tr.find(sy); if(px.F >= 0 && py.F >= 0) { swp.add_qry(i, px, py); } } int* ans = swp.solve(n); For(i, 1, q) { cout << ans[i] << "\n"; } return 0; } /* 2 3 AUGC AGC G C AU C A C => 0 1 2 3 3 AA AA AGA AA AA AG GA AG GA => 2 1 1 8 7 GCGCUACCCCAACACAAGGCAAGAUAUA G GGAC GCGG U GCGCUACCCCAACACAAGGCAAGAUGGUC GCCG GCGCUGA GCGCUACCC A GCGCUACCCC AC GCG C GCGC A G G G C G GGA => 1 0 1 2 3 2 0 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...