제출 #1139215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139215		Noproblem29	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	208 ms	193260 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#define ll long long
// #define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e5+100;
const int M=3e5+100;
const int B=447;
const int mod=998244353;
const ll INF=1e18;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;

int shrink(char x){
    if(x=='A')return 0;
    if(x=='G')return 1;
    if(x=='C')return 2;
    if(x=='U')return 3;
    return 5;
}
struct node{
    node *to[4];
    vector<int>val;
};
node ram[3000000];int point=0;
node *alloc(){
    node *res=&(ram[point++]);
    for(int j=0;j<4;j++){
        res->to[j]=nullptr;
    }
    return res;
}
int n,m;
string s[N],p[N],q[N];
node *trie,*trie_rev;
int px[N],py[N],lx[N],rx[N],ly[N],ry[N];
void append(node *cur,string &x,int pos){
    for(int i=0;i<x.size();i++){
        int c=x[i];
        if(!cur->to[c]){
            cur->to[c]=alloc();
        }
        cur=cur->to[c];
    }
    cur->val.push_back(pos);
}
void dfs(node *cur,int *tin,int *pr,int *l,int *r){
    if(cur==nullptr)return;
    for(auto i:cur->val){
        if(i<0){
            l[-i]=*tin;
        }
    }
    for(auto i:cur->val){
        if(i>0){
            pr[i]=(*tin)++;
        }
    }
    for(int i=0;i<4;i++){
        dfs(cur->to[i],tin,pr,l,r);
    }
    for(auto i:cur->val){
        if(i<0){
            r[-i]=*tin;
        }
    }
}
struct query{
    int pos,type,tl,tr;
    query(int pos=0,int type=0,int tl=0,int tr=0) : pos(pos),type(type),tl(tl),tr(tr){}
};
bool operator<(const query &x,const query &y){
    if(x.pos==y.pos){
        return x.type<y.type;
    }
    return x.pos<y.pos;
}
int ans[N];
int f[M];
void upd(int r,int y){
    ++r;
    for(;r<M;r+=((-r)&r)){
        f[r]+=y;
    }
}
int calc(int r){
    int res=0;
    ++r;
    for(;r>0;r-=((-r)&r)){
        res+=f[r];
    }
    return res;
}
int calc(int l,int r){
    return calc(r-1)-calc(l-1);
}
void test(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(auto &j:s[i]){
            j=shrink(j);
        }
    }
    for(int i=1;i<=m;i++){
        cin>>p[i];
        for(auto &j:p[i]){
            j=shrink(j);
        }
        cin>>q[i];
        for(auto &j:q[i]){
            j=shrink(j);
        }
    }
    trie=alloc();
    trie_rev=alloc();
    for(int i=1;i<=n;i++){
        append(trie,s[i],i);
        reverse(s[i].begin(),s[i].end());
        append(trie_rev,s[i],i);
    }
    for(int i=1;i<=m;i++){
        append(trie,p[i],-i);
        reverse(q[i].begin(),q[i].end());
        append(trie_rev,q[i],-i);
    }
    
    int tin=0;
    dfs(trie,&tin,px,lx,rx);

    tin=0;
    dfs(trie_rev,&tin,py,ly,ry);
    
    for(int i=1;i<=m;i++){
        ans[i]=0;
    }
    vector<query>v;
    for(int i=1;i<=n;i++){
        v.push_back(query(px[i],1e9,py[i]));
        // cout<<px[i]<<' '<<py[i]<<'\n';
    }
    for(int i=1;i<=m;i++){
        v.push_back(query(lx[i],-i,ly[i],ry[i]));
        v.push_back(query(rx[i],i,ly[i],ry[i]));
        // cout<<lx[i]<<' '<<rx[i]<<' '<<ly[i]<<' '<<ry[i]<<'\n';
    }
    // return;
    sort(v.begin(),v.end());
    for(query&i:v){
        if(i.type==1e9){
            upd(i.tl,1);
            continue;
        }
        if(i.type>0){
            ans[i.type]+=calc(i.tl,i.tr);
        }
        else{
            ans[-i.type]-=calc(i.tl,i.tr);
        }
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<'\n';
    }
}



/*

*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    int t2=1;
    // cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40