답안 #68055 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68055	2018-08-15T20:03:47 Z	duality	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	303 ms	190592 KB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#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+5];
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+5; 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

selling_rna.cpp: In function 'int doDFS(int)':
selling_rna.cpp:25: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:35: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:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < s1.size(); j++) {
                     ~~^~~~~~~~~~~
selling_rna.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < s1.size(); j++) {
                     ~~^~~~~~~~~~~
selling_rna.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < s1.size(); j++) {
                     ~~^~~~~~~~~~~
selling_rna.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j >= s1.size()) {
             ~~^~~~~~~~~~~~
selling_rna.cpp:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0; j < s2.size(); j++) {
                         ~~^~~~~~~~~~~
selling_rna.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (j >= s2.size()) {
                 ~~^~~~~~~~~~~~
selling_rna.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < Q.size(); i++) {
                 ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	94548 KB	Output is correct
2	Correct	91 ms	94688 KB	Output is correct
3	Correct	91 ms	94688 KB	Output is correct
4	Correct	86 ms	94688 KB	Output is correct
5	Correct	82 ms	94688 KB	Output is correct
6	Correct	100 ms	94688 KB	Output is correct
7	Correct	83 ms	94688 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	240 ms	147832 KB	Output is correct
2	Correct	229 ms	150228 KB	Output is correct
3	Correct	234 ms	150228 KB	Output is correct
4	Correct	226 ms	150844 KB	Output is correct
5	Correct	303 ms	171720 KB	Output is correct
6	Correct	281 ms	175336 KB	Output is correct
7	Correct	121 ms	175336 KB	Output is correct
8	Correct	220 ms	175336 KB	Output is correct
9	Correct	201 ms	175336 KB	Output is correct
10	Correct	165 ms	175336 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	148 ms	175336 KB	Output is correct
2	Correct	121 ms	175336 KB	Output is correct
3	Correct	151 ms	175336 KB	Output is correct
4	Correct	142 ms	175336 KB	Output is correct
5	Correct	142 ms	175336 KB	Output is correct
6	Correct	147 ms	175336 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	94548 KB	Output is correct
2	Correct	91 ms	94688 KB	Output is correct
3	Correct	91 ms	94688 KB	Output is correct
4	Correct	86 ms	94688 KB	Output is correct
5	Correct	82 ms	94688 KB	Output is correct
6	Correct	100 ms	94688 KB	Output is correct
7	Correct	83 ms	94688 KB	Output is correct
8	Correct	240 ms	147832 KB	Output is correct
9	Correct	229 ms	150228 KB	Output is correct
10	Correct	234 ms	150228 KB	Output is correct
11	Correct	226 ms	150844 KB	Output is correct
12	Correct	303 ms	171720 KB	Output is correct
13	Correct	281 ms	175336 KB	Output is correct
14	Correct	121 ms	175336 KB	Output is correct
15	Correct	220 ms	175336 KB	Output is correct
16	Correct	201 ms	175336 KB	Output is correct
17	Correct	165 ms	175336 KB	Output is correct
18	Correct	148 ms	175336 KB	Output is correct
19	Correct	121 ms	175336 KB	Output is correct
20	Correct	151 ms	175336 KB	Output is correct
21	Correct	142 ms	175336 KB	Output is correct
22	Correct	142 ms	175336 KB	Output is correct
23	Correct	147 ms	175336 KB	Output is correct
24	Correct	216 ms	183628 KB	Output is correct
25	Correct	256 ms	189308 KB	Output is correct
26	Correct	199 ms	190592 KB	Output is correct
27	Correct	258 ms	190592 KB	Output is correct
28	Correct	289 ms	190592 KB	Output is correct
29	Correct	236 ms	190592 KB	Output is correct

답안 #68055

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0