제출 #493211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493211		alextodoran	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	190 ms	175692 KiB

selling_rna

/**
 ____ ____ ____ ____ ____
||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) {
    curr++;
    int L = curr;
    for (int enc = 0; enc < 4; enc++) {
        if (node->son[enc] != NULL) {
            linearize(node->son[enc], curr);
        }
    }
    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;
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> P[i] >> Q[i];
    }
 
    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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40