oj.uz

Submission #320509

# Submission time Handle Problem Language Result Execution time Memory
320509 2020-11-09T01:08:16 Z thecodingwizard Selling RNA Strands (JOI16_selling_rna) C++11
10 / 100
 1500 ms 16080 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 100000
int n, m; 
vector<pair<string, int>> A, B;
vector<int> points[maxn];
ii strings[maxn];
int qryAns[maxn];
// <<x, y>, <i, mult>>
// add mult*(query [x, y]) to qryAns[i]
vector<pair<ii, ii>> queries[maxn];

ii findRange(vector<pair<string, int>> &list, string s) {
    ii res = mp(-1, -1);
    for (int i = 0; i < (int)list.size(); i++) {
        if (list[i].f.rfind(s, 0) == 0) {
            res.s = i;
            if (res.f == -1) res.f = i;
        }
    }
    return res;
}

int bit[maxn+10];
void upd(int k, int v) {
    k++;
    if (k <= 0) return;
    while (k <= n+5) {
        bit[k]+=v;
        k += k&-k;
    }
}
int qry(int k) {
    k++;
    if (k <= 0) return 0;
    int s = 0;
    while (k) {
        s += bit[k];
        k -= k&-k;
    }
    return s;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    F0R(i, n) {
        string s; cin >> s;
        A.pb(mp(s, i));
        reverse(all(s));
        B.pb(mp(s, i));
    }
    sort(all(A));
    sort(all(B));
    F0R(i, n) {
        strings[A[i].s].f = i;
        strings[B[i].s].s = i;
    }
    F0R(i, n) {
        //cout << "a point: " << strings[i].f << ", " << strings[i].s << endl;
        points[strings[i].f].pb(strings[i].s);
    }
    F0R(i, n) {
        //cout << i << ": " << A[i].f << endl;
    }
    F0R(i, n) {
        //cout << i << ": " << B[i].f << endl;
    }

    F0R(i, m) {
        string a, b; cin >> a >> b; reverse(all(b));
        ii prefixRange = findRange(A, a);
        ii suffixRange = findRange(B, b);
        //cout << a << "; " << b << ": [" << prefixRange.f << "," << prefixRange.s << "] and [" << suffixRange.f << "," << suffixRange.s << "]" << endl;
        if (prefixRange.f-1 >= 0) queries[prefixRange.f-1].pb(mp(suffixRange, mp(i, -1)));
        if (prefixRange.s >= 0) queries[prefixRange.s].pb(mp(suffixRange, mp(i, 1)));
    }

    F0R(i, n) {
        for (int x : points[i]) {
            upd(x, 1);
            //cout << "updating " << x << endl;
        }
        for (auto x : queries[i]) {
            //cout << "adding " << x.s.s << "*[" << x.f.f << "," << x.f.s << "] to " << x.s.f << endl;
            qryAns[x.s.f] += x.s.s*(qry(x.f.s)-qry(x.f.f-1));
        }
    }
    F0R(i, m) cout << qryAns[i] << endl;

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 9444 KB Output is correct
2 Correct 856 ms 14108 KB Output is correct
3 Correct 612 ms 13836 KB Output is correct
4 Correct 863 ms 14188 KB Output is correct
5 Correct 833 ms 11164 KB Output is correct
6 Correct 866 ms 11172 KB Output is correct
7 Correct 451 ms 14052 KB Output is correct
8 Execution timed out 1567 ms 16080 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 185 ms 9444 KB Output is correct
9 Correct 856 ms 14108 KB Output is correct
10 Correct 612 ms 13836 KB Output is correct
11 Correct 863 ms 14188 KB Output is correct
12 Correct 833 ms 11164 KB Output is correct
13 Correct 866 ms 11172 KB Output is correct
14 Correct 451 ms 14052 KB Output is correct
15 Execution timed out 1567 ms 16080 KB Time limit exceeded
16 Halted 0 ms 0 KB -