oj.uz

Submission #1048156

# Submission time Handle Problem Language Result Execution time Memory
1048156 2024-08-08T03:09:57 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 53 ms 18748 KB 
#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[11000111];         // 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 = max(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, 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 max(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 << get(ver[tr + 1], 0, n-1, l, r) - get(ver[tl], 0, n-1, l, r) << '\n';
    }
}

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 18748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -