oj.uz

Submission #493210

# Submission time Handle Problem Language Result Execution time Memory
493210 2021-12-10T11:26:46 Z alextodoran Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 163116 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int M_MAX = 100000;
const int XY_MAX = 2000000 * 3;

const int MOD = (int) 1e9 + 7;

int N, M;

string S[N_MAX];
string P[M_MAX], Q[M_MAX];

char chars[] = {'A', 'C', 'G', 'U'};
int encrypt[CHAR_MAX];

struct TrieNode {
    TrieNode* son[4];
    vector <pair <int, int>*> addresses;
    TrieNode () {
        for (int enc = 0; enc < 4; enc++) {
            son[enc] = NULL;
        }
        addresses.clear();
    }
};

void insertString (TrieNode* node, pair <int, int>* addr, string &str, string::iterator it) {
    if (it == str.end()) {
        node->addresses.push_back(addr);
        return;
    }
    int enc = encrypt[(int) *it];
    if (node->son[enc] == NULL) {
        node->son[enc] = new TrieNode;
    }
    insertString(node->son[enc], addr, str, next(it));
}
void insertString (TrieNode* root, pair <int, int>* addr, string &str) {
    insertString(root, addr, str, str.begin());
}

void linearize (TrieNode* node, int &curr, string str = "") {
    curr++;
    int L = curr;
    for (int enc = 0; enc < 4; enc++) {
        if (node->son[enc] != NULL) {
            linearize(node->son[enc], curr, str + chars[enc]);
        }
    }
    int R = curr;
    for (pair <int, int>* addr : node->addresses) {
        *addr = make_pair(L, R);
    }
}
void linearize (TrieNode* root) {
    int curr = 0;
    linearize(root, curr);
}

pair <int, int> SPrange[N_MAX];
pair <int, int> SQrange[N_MAX];
pair <int, int> Prange[N_MAX];
pair <int, int> Qrange[N_MAX];

TrieNode* rootP = new TrieNode;
TrieNode* rootQ = new TrieNode;

struct Point {
    int x, y;
};
bool operator < (const Point &p1, const Point &p2) {
    return p1.x < p2.x;
}

struct Query {
    Point p;
    int* addr;
    int sgn;
};
bool operator < (const Query &q1, const Query &q2) {
    return q1.p < q2.p;
}

Point points[N_MAX];
Query queries[M_MAX * 4];

int answer[M_MAX];

int Fen[XY_MAX + 2];

void updateFen (int y) {
    for (int i = y; i <= XY_MAX; i += i & -i) {
        Fen[i]++;
    }
}
int queryFen (int y) {
    int cnt = 0;
    for (int i = y; i >= 1; i -= i & -i) {
        cnt += Fen[i];
    }
    return cnt;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for (int enc = 0; enc < 4; enc++) {
        encrypt[(int) chars[enc]] = enc;
    }

    cin >> N >> M;
//    N = M = 100000;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
//        for (int j = 0; j < 20; j++) {
//            S[i] += chars[rand() % 4];
//        }
    }
    for (int i = 0; i < M; i++) {
        cin >> P[i] >> Q[i];
//        for (int j = 0; j < 20; j++) {
//            P[i] += chars[rand() % 4];
//            Q[i] += chars[rand() % 4];
//        }
    }

    for (int i = 0; i < N; i++) {
        insertString(rootP, &SPrange[i], S[i]);
        reverse(S[i].begin(), S[i].end());
        insertString(rootQ, &SQrange[i], S[i]);
    }
    for (int i = 0; i < M; i++) {
        insertString(rootP, &Prange[i], P[i]);
        reverse(Q[i].begin(), Q[i].end());
        insertString(rootQ, &Qrange[i], Q[i]);
    }
    linearize(rootP);
    linearize(rootQ);

    for (int i = 0; i < N; i++) {
        points[i] = Point{SPrange[i].first, SQrange[i].first};
    }
    for (int i = 0; i < M; i++) {
        queries[i * 4 + 0] = Query{Point{Prange[i].second,     Qrange[i].second},     &answer[i], +1};
        queries[i * 4 + 1] = Query{Point{Prange[i].first - 1,  Qrange[i].second},     &answer[i], -1};
        queries[i * 4 + 2] = Query{Point{Prange[i].second,     Qrange[i].first - 1},  &answer[i], -1};
        queries[i * 4 + 3] = Query{Point{Prange[i].first - 1,  Qrange[i].first - 1},  &answer[i], +1};
    }
    sort(points, points + N);
    sort(queries, queries + M * 4);

    for (int i = 0, j = -1; i < M * 4; i++) {
        while (j + 1 < N && points[j + 1].x <= queries[i].p.x) {
            j++;
            updateFen(points[j].y);
        }
        *queries[i].addr += queries[i].sgn * queryFen(queries[i].p.y);
    }

    for (int i = 0; i < M; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 KB Output is correct
2 Correct 5 ms 9804 KB Output is correct
3 Correct 5 ms 9804 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 6 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1560 ms 163116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19184 KB Output is correct
2 Correct 28 ms 15992 KB Output is correct
3 Correct 33 ms 17724 KB Output is correct
4 Correct 28 ms 16072 KB Output is correct
5 Correct 29 ms 15996 KB Output is correct
6 Correct 35 ms 17788 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 KB Output is correct
2 Correct 5 ms 9804 KB Output is correct
3 Correct 5 ms 9804 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 5 ms 9804 KB Output is correct
6 Correct 6 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Execution timed out 1560 ms 163116 KB Time limit exceeded
9 Halted 0 ms 0 KB -