oj.uz

Submission #202714

# Submission time Handle Problem Language Result Execution time Memory
202714 2020-02-17T20:49:30 Z tri Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 515 ms 50080 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


const int MAXN = 1e5 + 10;
const int MAXT = 3 * MAXN;

string nxt(string inp) {
    inp[inp.size() - 1]++;
    return inp;
}

string texts[MAXN];
string rTexts[MAXN];

struct rComp : binary_function<int, int, bool> {
    bool operator()(int a, int b) const {
        int cVal = rTexts[a].compare(rTexts[b]);
        if (cVal < 0) return true;
        if (cVal == 0) return a > b;
        return false;
    }
};

typedef tree<
        int,
        null_type,
        rComp,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;


int N, Q;

pair<pair<string, string>, int> fullQueries[MAXN];

ordered_set actInd;

int ans[MAXN];

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

    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        cin >> texts[i];
    }

    for (int i = 0; i < Q; i++) {
        cin >> fullQueries[i].f.f;
        cin >> fullQueries[i].f.s;
        fullQueries[i].s = i;
    }

    sort(texts, texts + N);

    for (int i = 0; i < N; i++) {
        rTexts[i] = texts[i];
        reverse(rTexts[i].begin(), rTexts[i].end());
//        ps(texts[i]);
    }

    sort(fullQueries, fullQueries + Q);

    int nTI = 0;

    vector<pair<pair<string, string>, int>> halfQueries;

    for (int i = 0; i < Q; i++) {
        halfQueries.pb({{nxt(fullQueries[i].f.f), fullQueries[i].f.s}, fullQueries[i].s});
        halfQueries.pb({{fullQueries[i].f.f, fullQueries[i].f.s}, fullQueries[i].s + Q});
    }

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

    fill(ans, ans + MAXN, 0);

    // queries are sorted by start string
    for (auto &cQ : halfQueries) {
        string cLast = cQ.f.f;

//        ps(cLast);

        while (nTI < N && texts[nTI] < cLast) {
            actInd.insert(nTI);
            nTI++;
        }

//        ps(actInd.size());

//        ps(actInd);

        string qFirst = cQ.f.s;
        reverse(qFirst.begin(), qFirst.end());

        string qLast = nxt(qFirst);

//        ps(qFirst, qLast);

        rTexts[N] = qLast;
        int c2 = actInd.order_of_key(N);

        rTexts[N] = qFirst;
        int c1 = actInd.order_of_key(N);

//        ps(c1, c2);

        int cAns = c2 - c1;
//        ps("cAns:", cAns);
        if (cQ.s < Q) {
            ans[cQ.s] += cAns;
        } else {
            ans[cQ.s - Q] -= cAns;
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << "\n";
    }
    cout << flush;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14072 KB Output is correct
2 Correct 14 ms 14072 KB Output is correct
3 Correct 14 ms 14072 KB Output is correct
4 Correct 13 ms 14072 KB Output is correct
5 Correct 14 ms 14072 KB Output is correct
6 Correct 15 ms 14072 KB Output is correct
7 Correct 15 ms 14200 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 28644 KB Output is correct
2 Correct 65 ms 29176 KB Output is correct
3 Correct 70 ms 29176 KB Output is correct
4 Correct 74 ms 29332 KB Output is correct
5 Correct 60 ms 24188 KB Output is correct
6 Correct 60 ms 24316 KB Output is correct
7 Correct 82 ms 35624 KB Output is correct
8 Correct 76 ms 37244 KB Output is correct
9 Correct 84 ms 37372 KB Output is correct
10 Correct 58 ms 27388 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 24140 KB Output is correct
2 Correct 129 ms 19804 KB Output is correct
3 Correct 160 ms 23388 KB Output is correct
4 Correct 145 ms 23388 KB Output is correct
5 Correct 128 ms 20188 KB Output is correct
6 Correct 174 ms 23384 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14072 KB Output is correct
2 Correct 14 ms 14072 KB Output is correct
3 Correct 14 ms 14072 KB Output is correct
4 Correct 13 ms 14072 KB Output is correct
5 Correct 14 ms 14072 KB Output is correct
6 Correct 15 ms 14072 KB Output is correct
7 Correct 15 ms 14200 KB Output is correct
8 Correct 44 ms 28644 KB Output is correct
9 Correct 65 ms 29176 KB Output is correct
10 Correct 70 ms 29176 KB Output is correct
11 Correct 74 ms 29332 KB Output is correct
12 Correct 60 ms 24188 KB Output is correct
13 Correct 60 ms 24316 KB Output is correct
14 Correct 82 ms 35624 KB Output is correct
15 Correct 76 ms 37244 KB Output is correct
16 Correct 84 ms 37372 KB Output is correct
17 Correct 58 ms 27388 KB Output is correct
18 Correct 221 ms 24140 KB Output is correct
19 Correct 129 ms 19804 KB Output is correct
20 Correct 160 ms 23388 KB Output is correct
21 Correct 145 ms 23388 KB Output is correct
22 Correct 128 ms 20188 KB Output is correct
23 Correct 174 ms 23384 KB Output is correct
24 Correct 128 ms 32348 KB Output is correct
25 Correct 240 ms 37836 KB Output is correct
26 Correct 89 ms 30436 KB Output is correct
27 Correct 166 ms 32376 KB Output is correct
28 Correct 515 ms 50080 KB Output is correct
29 Correct 457 ms 36756 KB Output is correct