제출 #1307598

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

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2100050,inf=1e9;
void chmn(int &x,int y){x=min(x,y);}
void chmx(int &x,int y){x=max(x,y);}
int n,q;
string S[N];
void Sredi(string &s){
    for(auto &i:s){
        if(i=='C')i='B';
        if(i=='G')i='C';
        if(i=='U')i='D';
    }
}
struct Trie{
    int root,nc,numc,go[N][4];
    vector<int>indexes[N];
    Trie(){indm[0]=inf;indM[0]=-1;}
    void Update(int &c,string &s,int i=0){
        if(!c)c=++nc;
        if(i>=s.size()){
            indexes[c].pb(numc++);
            return;
        }
        Update(go[c][s[i]-'A'],s,i+1);
    }
    int indm[N],indM[N];
    vector<int>ind;
    void DFS(int u){
        indm[u]=inf;indM[u]=-1;
        if(indexes[u].size()){
            indm[u]=ind.size();
            for(auto i:indexes[u])ind.pb(i);
            indM[u]=(int)ind.size()-1;
        }
        for(int i=0;i<4;i++)if(go[u][i]){
            DFS(go[u][i]);
            chmn(indm[u],indm[go[u][i]]);
            chmx(indM[u],indM[go[u][i]]);
        }
    }
    int Get(int c,string &s,int i=0){
        if(i>=s.size()) return c;
        return Get(go[c][s[i]-'A'],s,i+1);
    }
    void Insert(string &s){Update(root,s);}
    pair<int,int>Get(string &s){int u=Get(root,s);return {indm[u],indM[u]};}
}trie[2];
struct BIT{
    int T[N+5];
    void Update(int i,int x){i++;for(;i<=N;i+=i&-i)T[i]+=x;}
    int Get(int i){i++;int x=0;for(;i>=1;i-=i&-i)x+=T[i];return x;}
    int Get(int l,int r){return Get(r)-Get(l-1);}
}bt;
vector<array<int,4>>ev[N];
int main(){
    scanf("%i%i",&n,&q);
    for(int i=0;i<n;i++){
        cin>>S[i];
        Sredi(S[i]);
    }
    for(int i=0;i<n;i++){
        trie[0].Insert(S[i]);
        reverse(S[i].begin(),S[i].end());
        trie[1].Insert(S[i]);
        reverse(S[i].begin(),S[i].end());
    }
    trie[0].DFS(trie[0].root);
    trie[1].DFS(trie[1].root);
    int res[q+5]={0};
    for(int I=0;I<q;I++){
        string P,Q;cin>>P>>Q;
        Sredi(P);Sredi(Q);
        reverse(Q.begin(),Q.end());
        auto [Lp,Rp]=trie[0].Get(P);
        auto [Lq,Rq]=trie[1].Get(Q);
        if(Lp<=Rp&&Lq<=Rq){
            ev[Rp].pb({Lq,Rq,1,I});
            if(Lp>0)ev[Lp-1].pb({Lq,Rq,-1,I});
        }
    }
    vector<int>P=trie[0].ind,Q=trie[1].ind,invQ(n);
    for(int i=0;i<n;i++)invQ[Q[i]]=i;
    for(int i=0;i<n;i++){
        bt.Update(invQ[P[i]],1);
        for(auto [l,r,bit,I]:ev[i])res[I]+=bit*bt.Get(l,r);
    }
    for(int i=0;i<q;i++)printf("%i\n",res[i]);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%i%i",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~

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