Submission #68117

#TimeUsernameProblemLanguageResultExecution timeMemory
68117dualitySelling RNA Strands (JOI16_selling_rna)C++11
100 / 100
328 ms165548 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- #define SIZE 2000000 int index(char c) { if (c == 'A') return 0; else if (c == 'C') return 1; else if (c == 'G') return 2; else return 3; } int trie[SIZE+1][4],num = 0; int trie2[SIZE+1][4],num2 = 0; vi leaf[SIZE+1],leaf2[SIZE+1]; int disc[SIZE+1],disc2[SIZE+1]; int fin[SIZE+1],fin2[SIZE+1]; pii points[100000]; int doDFS(int u) { int i; disc[u] = num++; for (i = 0; i < leaf[u].size(); i++) points[leaf[u][i]].first = num-1; for (i = 0; i < 4; i++) { if (trie[u][i] != 0) doDFS(trie[u][i]); } fin[u] = num-1; return 0; } int doDFS2(int u) { int i; disc2[u] = num2++; for (i = 0; i < leaf2[u].size(); i++) points[leaf2[u][i]].second = num2-1; for (i = 0; i < 4; i++) { if (trie2[u][i] != 0) doDFS2(trie2[u][i]); } fin2[u] = num2-1; return 0; } vector<pair<pii,int> > Q; int ans[100000]; int bit[SIZE]; int main() { cin.sync_with_stdio(0); int i,j; int N,M; string s1,s2; cin >> N >> M; for (i = 0; i < N; i++) { cin >> s1; int c = 0; for (j = 0; j < s1.size(); j++) { if (trie[c][index(s1[j])] == 0) trie[c][index(s1[j])] = ++num; c = trie[c][index(s1[j])]; } leaf[c].pb(i); reverse(s1.begin(),s1.end()); c = 0; for (j = 0; j < s1.size(); j++) { if (trie2[c][index(s1[j])] == 0) trie2[c][index(s1[j])] = ++num2; c = trie2[c][index(s1[j])]; } leaf2[c].pb(i); } num = num2 = 0; doDFS(0),doDFS2(0); for (i = 0; i < N; i++) Q.pb(mp(points[i],-1e9)); for (i = 0; i < M; i++) { cin >> s1 >> s2; int c = 0; for (j = 0; j < s1.size(); j++) { if (trie[c][index(s1[j])] == 0) break; c = trie[c][index(s1[j])]; } if (j >= s1.size()) { int c2 = 0; reverse(s2.begin(),s2.end()); for (j = 0; j < s2.size(); j++) { if (trie2[c2][index(s2[j])] == 0) break; c2 = trie2[c2][index(s2[j])]; } if (j >= s2.size()) { Q.pb(mp(mp(fin[c],fin2[c2]),i+1)); Q.pb(mp(mp(disc[c]-1,fin2[c2]),-(i+1))); Q.pb(mp(mp(fin[c],disc2[c2]-1),-(i+1))); Q.pb(mp(mp(disc[c]-1,disc2[c2]-1),i+1)); } } } sort(Q.begin(),Q.end()); for (i = 0; i < Q.size(); i++) { if (Q[i].second == -1e9) { for (j = Q[i].first.second+1; j < SIZE; j += j & (-j)) bit[j]++; } else { int s = 0; for (j = Q[i].first.second+1; j > 0; j -= j & (-j)) s += bit[j]; if (Q[i].second < 0) ans[-Q[i].second-1] -= s; else ans[Q[i].second-1] += s; } } for (i = 0; i < M; i++) printf("%d\n",ans[i]); return 0; }

Compilation message (stderr)

selling_rna.cpp: In function 'int doDFS(int)':
selling_rna.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < leaf[u].size(); i++) points[leaf[u][i]].first = num-1;
                 ~~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int doDFS2(int)':
selling_rna.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < leaf2[u].size(); i++) points[leaf2[u][i]].second = num2-1;
                 ~~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < s1.size(); j++) {
                     ~~^~~~~~~~~~~
selling_rna.cpp:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < s1.size(); j++) {
                     ~~^~~~~~~~~~~
selling_rna.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < s1.size(); j++) {
                     ~~^~~~~~~~~~~
selling_rna.cpp:127:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j >= s1.size()) {
             ~~^~~~~~~~~~~~
selling_rna.cpp:130:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < s2.size(); j++) {
                         ~~^~~~~~~~~~~
selling_rna.cpp:134:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j >= s2.size()) {
                 ~~^~~~~~~~~~~~
selling_rna.cpp:144:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < Q.size(); 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...