제출 #866792

#제출 시각아이디문제언어결과실행 시간메모리
866792catloverSelling RNA Strands (JOI16_selling_rna)C++14
100 / 100
258 ms297940 KiB
// cre: Nguyen Hoang Hung - Train VOI 2024 #include <bits/stdc++.h> #define int long long #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a->begin()) it = a->begin(); it != a->end(); ++it) #define debug(x) { cerr << #x << " = "; cerr << (x) << endl; } #define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; } #define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; } #define bit(X, i) ((X >> i) & 1) #define cntbit(X) __builtin_popcountll(X) #define fi first #define se second #define pb push_back #define all(X) begin(X), end(X) #define SZ(X) ((int)(X).size()) #define RR(X) X->resize(unique(all(X)) - begin(X)) #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; template <typename T> bool maximize(T &x, T y) { if(x < y) x = y; else return 0; return 1; } template <typename T> bool minimize(T &x, T y) { if(x > y) x = y; else return 0; return 1; } typedef long long ll; typedef long double ld; typedef pair<int, int> pii; ll Rand(ll l, ll r) { return l + rand() % (r - l + 1); } const int maxN = 2e6; const ll inf = 1e18+7; const int MOD = 1e9 + 7; const double PI = acos(-1); /* ------------------------------------------------------------------------------------- END OF TEMPLATE ------------------------------------------------------------------------------------- Nguyen Hoang Hung - catlover Training for VOI24 gold medal ------------------------------------------------------------------------------------- */ int N, M, pos[maxN]; string s[maxN]; int convert(char c) { if(c == 'A') return 0; if(c == 'G') return 1; if(c == 'C') return 2; return 3; } ////////////////////////////////////////////////// /** BUILD TRIE **/ struct Trie { Trie *child[4]; int tin, tout; vector<int> vt; Trie() { FOR(i, 0, 3) child[i] = NULL; tin = tout = 0; vt.resize(0); } }; Trie T, T_rev; void add(string s, int id) { Trie *p = &T; FOR(i, 0, SZ(s)-1) { int c = convert(s[i]); if (p->child[c] == NULL) p->child[c] = new Trie(); p = p->child[c]; } p->vt.pb(id); } void add_rev(string s, int id) { Trie *p = &T_rev; FOR(i, 0, SZ(s)-1) { int c = convert(s[i]); if (p->child[c] == NULL) p->child[c] = new Trie(); p = p->child[c]; p->vt.pb(pos[id]); } } ////////////////////////////////////////////////// /** EULER TOUR **/ int Time = 0; void dfs(Trie *p) { p->tin = ++Time; if(p->vt.size()) { for(auto x : p->vt) pos[x] = Time; } FOR(i, 0, 3) { if(p->child[i] == NULL) continue; dfs(p->child[i]); } p->tout = Time; } void dfs_Rev(Trie *p) { sort(all(p->vt)); FOR(i, 0, 3) { if (p->child[i] == NULL) continue; dfs_Rev(p->child[i]); } } pii getRange(string s) { Trie *p = &T; FOR(i, 0, SZ(s)-1) { int c = convert(s[i]); if (p->child[c] == NULL) return make_pair(0, 0); p = p->child[c]; } return make_pair(p->tin, p->tout); } int getAns(string s, pii Range) { Trie *p = &T_rev; FOR(i, 0, SZ(s)-1) { int c = convert(s[i]); if (p->child[c] == NULL) return 0; p = p->child[c]; } int l = lower_bound(all(p->vt), Range.fi) - p->vt.begin(); int r = upper_bound(all(p->vt), Range.se) - p->vt.begin()-1; return (r - l + 1); } void solve() { cin >> N >> M; FOR(i, 1, N) cin >> s[i]; FOR(i, 1, N) add(s[i], i); dfs(&T); FOR(i, 1, N) reverse(all(s[i])); FOR(i, 1, N) add_rev(s[i], i); dfs_Rev(&T_rev); while(M --> 0) { string P, Q; cin >> P >> Q; reverse(all(Q)); pii R = getRange(P); // cout << R.fi << ' ' << R.se << endl; cout << getAns(Q, R) << '\n'; } } void solve_TestCase() { int testcase; cin >> testcase; while(testcase --> 0) { solve(); } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); file("RNA"); // solve_TestCase(); solve(); cerr << "\nTime : " << clock()/1000.0 << "s\n"; return 0; }

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

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:24:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:213:5: note: in expansion of macro 'file'
  213 |     file("RNA");
      |     ^~~~
selling_rna.cpp:24:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:213:5: note: in expansion of macro 'file'
  213 |     file("RNA");
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...