oj.uz

Submission #682897

# Submission time Handle Problem Language Result Execution time Memory
682897 2023-01-17T08:12:51 Z urosk Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 605 ms 709348 KB 
#include <bits/stdc++.h>
#define here cerr<<"=============================\n"
#define ll int
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define sz(a) (ll)(a.size())
#define pb push_back
#define llinf 100000000000000000LL
#define endl '\n'
#define pll pair<ll,ll>
#define all(a) a.begin(),a.end()
#define fi first
#define sc second
using namespace std;
#define maxn 8000005
#define maxx 30
ll n,q;
ll t[maxn][5];
ll t2[maxn],ls[maxn],rs[maxn];
ll L[maxn],L2[maxn],R[maxn],R2[maxn];
ll root,root2;
ll ti = 0,tsz = 1;
ll lid[maxn],rid[maxn];
ll in[maxn],out[maxn];
vector<ll> a[maxn];
vector<pll> v[maxn];
string ss[maxn];
map<char,ll> id;
void add(ll &v,string &s,ll i,ll d){
    if(!v) v = ++tsz;
    if(sz(s)==i||i==-1) return;
    ll c = id[s[i]];
    add(t[v][c],s,i+d,d);
}
void dfs(ll v){
    in[v] = ++ti;
    for(ll i = 0;i<4;i++){
        if(!t[v][i]) continue;
        dfs(t[v][i]);
    }
    out[v] = ti;
}
pll get(ll v,string &s,ll i,ll d){
    if(sz(s)==i||i==-1) return {in[v],out[v]};
    ll c = id[s[i]];
    if(t[v][c]==0) return {-1,-2};
    return get(t[v][c],s,i+d,d);
}
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
map<pair<pll,ll> ,ll> mp;
int main()
{
    id['A'] = 0;
    id['G'] = 1;
    id['U'] = 2;
    id['C'] = 3;
    cin >> n >> q;
    root = 1;
    root2 = 1;
    for(ll i = 1;i<=n;i++){
        string s; cin >> ss[i];
        s = ss[i];
        add(root,s,0,1);
    }
    dfs(root);
    root2 = ++tsz;
    for(ll i = 1;i<=n;i++){
        string s = ss[i];
        add(root2,s,sz(s)-1,-1);
    }
    ti = 0;
    dfs(root2);
    ll mx = tsz;
    for(ll i = 1;i<=n;i++){
        string s = ss[i];
        pll p = get(root,s,0,1);
        lid[i] = p.fi;
        p = get(root2,s,sz(s)-1,-1);
        rid[i] = p.fi;
        a[rid[i]].pb(lid[i]);
    }
    for(ll i = 1;i<=q;i++){
        string s; cin >> s;
        pll p = get(root,s,0,1);
        cin >> s;
        L[i] = p.fi,R[i] = p.sc;
        p = get(root2,s,sz(s)-1,-1);
        L2[i] = p.fi,R2[i] = p.sc;
        v[L2[i]-1].pb({L[i],R[i]});
        v[R2[i]].pb({L[i],R[i]});
    }
    tsz = 0;
    FenwickTree f(mx);
    for(ll i = 0;i<=mx;i++){
        for(ll x : a[i]){
            f.add(x,1);
        }
        for(pll p : v[i]){
            mp[{{p.fi,p.sc},i}] = f.sum(p.fi,p.sc);
        }
    }
    for(ll i = 1;i<=q;i++){
        cout<<mp[{{L[i],R[i]},R2[i]}] - mp[{{L[i],R[i]},L2[i]-1}]<<endl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 626528 KB Output is correct
2 Correct 313 ms 626604 KB Output is correct
3 Correct 291 ms 626688 KB Output is correct
4 Correct 322 ms 626604 KB Output is correct
5 Correct 286 ms 626600 KB Output is correct
6 Correct 293 ms 626556 KB Output is correct
7 Correct 286 ms 626508 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 695624 KB Output is correct
2 Correct 559 ms 692656 KB Output is correct
3 Correct 574 ms 695180 KB Output is correct
4 Correct 541 ms 692328 KB Output is correct
5 Correct 532 ms 708116 KB Output is correct
6 Correct 553 ms 709348 KB Output is correct
7 Correct 447 ms 634972 KB Output is correct
8 Correct 507 ms 680376 KB Output is correct
9 Correct 496 ms 673320 KB Output is correct
10 Correct 439 ms 669308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 629800 KB Output is correct
2 Correct 330 ms 628700 KB Output is correct
3 Correct 342 ms 629176 KB Output is correct
4 Correct 328 ms 628768 KB Output is correct
5 Correct 318 ms 628800 KB Output is correct
6 Correct 359 ms 629284 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 626528 KB Output is correct
2 Correct 313 ms 626604 KB Output is correct
3 Correct 291 ms 626688 KB Output is correct
4 Correct 322 ms 626604 KB Output is correct
5 Correct 286 ms 626600 KB Output is correct
6 Correct 293 ms 626556 KB Output is correct
7 Correct 286 ms 626508 KB Output is correct
8 Correct 563 ms 695624 KB Output is correct
9 Correct 559 ms 692656 KB Output is correct
10 Correct 574 ms 695180 KB Output is correct
11 Correct 541 ms 692328 KB Output is correct
12 Correct 532 ms 708116 KB Output is correct
13 Correct 553 ms 709348 KB Output is correct
14 Correct 447 ms 634972 KB Output is correct
15 Correct 507 ms 680376 KB Output is correct
16 Correct 496 ms 673320 KB Output is correct
17 Correct 439 ms 669308 KB Output is correct
18 Correct 324 ms 629800 KB Output is correct
19 Correct 330 ms 628700 KB Output is correct
20 Correct 342 ms 629176 KB Output is correct
21 Correct 328 ms 628768 KB Output is correct
22 Correct 318 ms 628800 KB Output is correct
23 Correct 359 ms 629284 KB Output is correct
24 Correct 547 ms 685672 KB Output is correct
25 Correct 605 ms 686828 KB Output is correct
26 Correct 542 ms 684644 KB Output is correct
27 Correct 554 ms 685416 KB Output is correct
28 Correct 566 ms 646732 KB Output is correct
29 Correct 479 ms 635156 KB Output is correct