oj.uz

Submission #341184

# Submission time Handle Problem Language Result Execution time Memory
341184 2020-12-29T05:15:15 Z rrrr10000 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 683 ms 337132 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k,t) (lower_bound(all(v),(k),t)-v.begin())
#define fi first
#define se second
#define dame(a) {out(a);return 0;}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll sz=4;
vector<string> str;
vector<pair<string,string>> query;
vi ans;
ll char_to_ll(char c){
    if(c=='A')return 0;
    if(c=='G')return 1;
    if(c=='C')return 2;
    if(c=='U')return 3;
}
vp stringnum;
vector<pair<P,P>> querynum;
class trie{
public:
    vvi ch,q;
    vp range;
    ll c=1,euler;
    vvi res;
    trie(ll k){
        ch=vvi(1,vi(sz,-1));
        res=vvi(1);
    }
    void insert(ll num){
        ll w=0;
        rep(i,str[num].size()){
            ll t=char_to_ll(str[num][i]);
            if(ch[w][t]==-1){
                ch[w][t]=c++;
                res.pb(vi(0));ch.pb(vi(4,-1));
                w=ch[w][t];
            }
            else{
                w=ch[w][t];
            }
        }
        res[w].pb(num);
    }
    void add_query(ll num){
        if(q.size()==0)q=vvi(c);
        ll w=0;
        rep(i,query[num].fi.size()){
            ll t=char_to_ll(query[num].fi[i]);
            if(ch[w][t]==-1)return;
            else w=ch[w][t];
        }
        q[w].pb(num);
    }
    void euler_tour(ll w){
        if(range.size()==0){
            euler=0;
            range=vp(c);
        }
        range[w].fi=euler++;
        rep(i,sz)if(ch[w][i]!=-1)euler_tour(ch[w][i]);
        range[w].se=euler;
        for(ll x:res[w])stringnum[x].fi=range[w].fi;
        for(ll x:q[w])querynum[x].fi=range[w];
    }
};
class rtrie{
public:
    vvi ch,q;
    vp range;
    ll c=1,euler;
    vvi res;
    rtrie(ll k){
        ch=vvi(1,vi(sz,-1));
        res=vvi(1);
    }
    void insert(ll num){
        ll w=0;
        for(int i=str[num].size()-1;i>=0;i--){
            ll t=char_to_ll(str[num][i]);
            if(ch[w][t]==-1){
                ch[w][t]=c++;
                res.pb(vi(0));ch.pb(vi(4,-1));
                w=ch[w][t];
            }
            else{
                w=ch[w][t];
            }
        }
        res[w].pb(num);
    }
    void add_query(ll num){
        if(q.size()==0)q=vvi(c);
        ll w=0;
        for(int i=query[num].se.size()-1;i>=0;i--){
            ll t=char_to_ll(query[num].se[i]);
            if(ch[w][t]==-1)return;
            else w=ch[w][t];
        }
        q[w].pb(num);
    }
    void euler_tour(ll w){
        if(range.size()==0){
            euler=0;
            range=vp(c);
        }
        range[w].fi=euler++;
        rep(i,sz)if(ch[w][i]!=-1)euler_tour(ch[w][i]);
        range[w].se=euler;
        for(ll x:res[w])stringnum[x].se=range[w].fi;
        for(ll x:q[w])querynum[x].se=range[w];
    }
};
    bool comp_y(P a,P b){
        if(a.se==b.se)return a.fi<b.fi;
        return a.se<b.se;
    }
class fractional_cascading{
public:
    ll N=1;vvp seg;
    vi L,R;
    fractional_cascading(vp v){
        sort(all(v));
        while(N<v.size())N*=2;
        seg=vvp(N*2-1);L=vi(N*2-1,inf);R=vi(N*2-1,-inf);
        rep(i,v.size())seg[i+N-1].pb(v[i]);
        rep(i,N)L[i+N-1]=R[i+N-1]=v[min(i,(ll)(v.size()-1))].fi;
        rep(i,N)R[i+N-1]++;
        for(int i=N-2;i>=0;i--){
            L[i]=L[i*2+1];R[i]=R[i*2+2];
            int a=0,b=0;
            while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
                if(b==seg[i*2+2].size())seg[i].pb(seg[i*2+1][a++]);
                else if(a==seg[i*2+1].size())seg[i].pb(seg[i*2+2][b++]);
                else if(comp_y(seg[i*2+1][a],seg[i*2+2][b]))seg[i].pb(seg[i*2+1][a++]);
                else seg[i].pb(seg[i*2+2][b++]);
            }
        }
    }
    ll range_sum(ll x1,ll x2,ll y1,ll y2,ll k=0){
        // cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<' '<<k<<endl;
        if(x1<=L[k]&&R[k]<=x2)return lb(seg[k],P(-inf,y2),comp_y)-lb(seg[k],P(-inf,y1),comp_y);
        if(R[k]<=x1||x2<=L[k])return 0;
        return range_sum(x1,x2,y1,y2,k*2+1)+range_sum(x1,x2,y1,y2,k*2+2);
    }
};
int main(){
    ll n,m;cin>>n>>m;
    str=vector<string>(n);
    query=vector<pair<string,string>>(m);
    stringnum=vp(n);querynum=vector<pair<P,P>>(m);
    ans=vi(m);
    rep(i,n)cin>>str[i];
    rep(i,m)cin>>query[i].fi>>query[i].se;
    trie tr(1);
    rtrie rtr(1);
    rep(i,n){
        tr.insert(i);
        rtr.insert(i);
    }
    rep(i,m){
        tr.add_query(i);
        rtr.add_query(i);
    }
    tr.euler_tour(0);rtr.euler_tour(0);
    fractional_cascading fac(stringnum);
    rep(i,m)out(fac.range_sum(querynum[i].fi.fi,querynum[i].fi.se,querynum[i].se.fi,querynum[i].se.se));
}

Compilation message

selling_rna.cpp: In constructor 'fractional_cascading::fractional_cascading(vp)':
selling_rna.cpp:147:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         while(N<v.size())N*=2;
      |               ~^~~~~~~~~
selling_rna.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
      |                   ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:155:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             while(a!=seg[i*2+1].size()||b!=seg[i*2+2].size()){
      |                                         ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:156:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |                 if(b==seg[i*2+2].size())seg[i].pb(seg[i*2+1][a++]);
      |                    ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:157:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |                 else if(a==seg[i*2+1].size())seg[i].pb(seg[i*2+2][b++]);
      |                         ~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'll char_to_ll(char)':
selling_rna.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 269748 KB Output is correct
2 Correct 507 ms 258380 KB Output is correct
3 Correct 513 ms 267836 KB Output is correct
4 Correct 499 ms 256124 KB Output is correct
5 Correct 650 ms 331892 KB Output is correct
6 Correct 653 ms 337132 KB Output is correct
7 Correct 166 ms 10476 KB Output is correct
8 Correct 516 ms 201432 KB Output is correct
9 Correct 468 ms 170380 KB Output is correct
10 Correct 372 ms 163468 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 30948 KB Output is correct
2 Correct 101 ms 18920 KB Output is correct
3 Correct 114 ms 27236 KB Output is correct
4 Correct 99 ms 23204 KB Output is correct
5 Correct 83 ms 18792 KB Output is correct
6 Correct 108 ms 27236 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 510 ms 269748 KB Output is correct
9 Correct 507 ms 258380 KB Output is correct
10 Correct 513 ms 267836 KB Output is correct
11 Correct 499 ms 256124 KB Output is correct
12 Correct 650 ms 331892 KB Output is correct
13 Correct 653 ms 337132 KB Output is correct
14 Correct 166 ms 10476 KB Output is correct
15 Correct 516 ms 201432 KB Output is correct
16 Correct 468 ms 170380 KB Output is correct
17 Correct 372 ms 163468 KB Output is correct
18 Correct 120 ms 30948 KB Output is correct
19 Correct 101 ms 18920 KB Output is correct
20 Correct 114 ms 27236 KB Output is correct
21 Correct 99 ms 23204 KB Output is correct
22 Correct 83 ms 18792 KB Output is correct
23 Correct 108 ms 27236 KB Output is correct
24 Correct 519 ms 232180 KB Output is correct
25 Correct 590 ms 236408 KB Output is correct
26 Correct 493 ms 228220 KB Output is correct
27 Correct 506 ms 229364 KB Output is correct
28 Correct 683 ms 104244 KB Output is correct
29 Correct 376 ms 65984 KB Output is correct