제출 #1048160

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

selling_rna

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second

const int N = 2e6 + 3;

int n, m;
string s, p, q;
vector<pair<string, int> > a, b;
int ans = 0;

//////////////////// Persistent IT

int nVer = 0;

struct Node {
    int left, right;    // ID of left child & right child
    long long ln;       // Max value of node
    Node() {}
    Node(long long ln, int left, int right) : ln(ln), left(left), right(right) {}
} it[1 << 21];         // Each node has a position in this array, called ID
int nNode;

const int MN = 1e5 + 3;
int ver[MN];            // ID of root in each version

// Update max value of a node
inline void refine(int cur) {
    it[cur].ln = (it[it[cur].left].ln + it[it[cur].right].ln);
}

// Update a range, and return new ID of node
int update(int l, int r, int u, int x, int oldId) {
    if (l == r) {
//        cout << l << ' ' << x << ' ' << nNode + 1 << '\n';
        ++nNode;
        it[nNode] = Node(x + it[nNode].ln, 0, 0);
        return nNode;
    }

    int mid = (l + r) >> 1;
    int cur = ++nNode;

    if (u <= mid) {
        it[cur].left = update(l, mid, u, x, it[oldId].left);
        it[cur].right = it[oldId].right;
        refine(cur);
    }
    else {
        it[cur].left = it[oldId].left;
        it[cur].right = update(mid+1, r, u, x, it[oldId].right);
        refine(cur);
    }

    return cur;
}

// Get max of range. Same as usual IT
int get(int nodeId, int l, int r, int u, int v) {
    if (v < l || r < u) return -1;
    if (u <= l && r <= v) return it[nodeId].ln;

    int mid = (l + r) >> 1;
    return (get(it[nodeId].left, l, mid, u, v) + get(it[nodeId].right, mid+1, r, u, v));
}


//// When update:
//    ++nVer;
//    ver[nVer] = update(1, n, u, x, ver[nVer-1]);
//
//// When query:
//    res = get(ver[t], 1, n, u, v);

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        cin >> s;
        a.push_back({s, i});
    }

    sort (a.begin(), a.end());
    for (int i = 0; i < n; ++ i) {
        s = a[i].fi;
        reverse(s.begin(), s.end());
        b.push_back({s, i});
    }

    sort (b.begin(), b.end());

    for (auto [s, id] : b) {
        ++ nVer;
        ver[nVer] = update(0, n - 1, id, 1, ver[nVer-1]);
    }

//    for (auto [s, id] : a) cout << s << '\n';
//    for (auto [s, id] : b) cout << s << ' ' << id << '\n';

    while (m --) {
        cin >> p >> q;
        reverse(q.begin(), q.end());

        int l = lower_bound(a.begin(), a.end(), make_pair(p, -1)) - a.begin();
        p.back() ++;
        int r = lower_bound(a.begin(), a.end(), make_pair(p, -1)) - a.begin() - 1;

        int tl = lower_bound(b.begin(), b.end(), make_pair(q, -1)) - b.begin();
        q.back() ++;
        int tr = lower_bound(b.begin(), b.end(), make_pair(q, -1)) - b.begin() - 1;

        if (l >= a.size() || tl >= b.size()) {
            cout << 0 << '\n';
            continue;
        }

//        cout << l << ' ' << r << ' ' << tl << ' ' << tr + 1 << '\n';
        cout << get(ver[tr + 1], 0, n-1, l, r) - get(ver[tl], 0, n-1, l, r) << '\n';
    }
}

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

selling_rna.cpp: In constructor 'Node::Node(long long int, int, int)':
selling_rna.cpp:22:15: warning: 'Node::ln' will be initialized after [-Wreorder]
   22 |     long long ln;       // Max value of node
      |               ^~
selling_rna.cpp:21:9: warning:   'int Node::left' [-Wreorder]
   21 |     int left, right;    // ID of left child & right child
      |         ^~~~
selling_rna.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Node(long long ln, int left, int right) : ln(ln), left(left), right(right) {}
      |     ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:118:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         if (l >= a.size() || tl >= b.size()) {
      |             ~~^~~~~~~~~~~
selling_rna.cpp:118:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         if (l >= a.size() || tl >= b.size()) {
      |                              ~~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40