제출 #320508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320508		thecodingwizard	Selling RNA Strands (JOI16_selling_rna)	C++11	0 / 100	1574 ms	13412 KiB

selling_rna

#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];
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) {
        points[A[i].s].pb(B[i].s);
    }

    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 " << i << " " << 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: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40