oj.uz

Submission #682733

# Submission time Handle Problem Language Result Execution time Memory
682733 2023-01-16T21:02:56 Z urosk Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 762420 KB 
#include <bits/stdc++.h>
#define here cerr<<"=============================\n"
#define ll long long
#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,root3;
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);
}
void upd(ll v,ll tl,ll tr,ll i,ll x){
    if(tl==tr){t2[v]+=x;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(ls[v],tl,mid,i,x);
    else upd(rs[v],mid+1,tr,i,x);
    t2[v] = t2[ls[v]] + t2[rs[v]];
}
ll sum(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r||tl>tr||tr<l||tl>r) return 0;
    if(tl>=l&&tr<=r) return t2[v];
    ll mid = (tl+tr)/2;
    return sum(ls[v],tl,mid,l,r) + sum(rs[v],mid+1,tr,l,r);
}
void init(ll &v,ll tl,ll tr){
    if(!v) v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
struct kv{
    ll l,r,d;
};
bool operator < (kv a,kv b){
    return a.d<b.d;
}
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 = n+q+1;
    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 = root3 = 0;
    init(root3,1,mx);
    for(ll i = 0;i<=mx;i++){
        for(ll x : a[i]){
            upd(root3,1,mx,x,1);
        }
        for(pll p : v[i]){
            mp[{{p.fi,p.sc},i}] = sum(root3,1,mx,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 270 ms 626636 KB Output is correct
2 Correct 271 ms 626648 KB Output is correct
3 Correct 270 ms 626664 KB Output is correct
4 Correct 283 ms 626624 KB Output is correct
5 Correct 267 ms 626592 KB Output is correct
6 Correct 273 ms 626632 KB Output is correct
7 Correct 270 ms 626764 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 635164 KB Output is correct
2 Correct 326 ms 632296 KB Output is correct
3 Correct 338 ms 633644 KB Output is correct
4 Correct 322 ms 632292 KB Output is correct
5 Correct 324 ms 632492 KB Output is correct
6 Correct 335 ms 633996 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 626636 KB Output is correct
2 Correct 271 ms 626648 KB Output is correct
3 Correct 270 ms 626664 KB Output is correct
4 Correct 283 ms 626624 KB Output is correct
5 Correct 267 ms 626592 KB Output is correct
6 Correct 273 ms 626632 KB Output is correct
7 Correct 270 ms 626764 KB Output is correct
8 Execution timed out 1617 ms 762420 KB Time limit exceeded
9 Halted 0 ms 0 KB -