제출 #286345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286345		LifeHappen__	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	260 ms	153336 KiB

selling_rna

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define forinc(a,b,c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a,b,c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a,b) for(auto &a:b)

#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

typedef long long ll;
typedef unsigned long long ull;

const int N=1e5+5;
int n,m,it=1;
string s[N],pf[N],sf[N];
map<char,int> dd;
int g[N*20][5],ma[N*20],mi[N*20],sz[N*20],ans[N];
vector<int> st[N],en[N];

void add(int i){
   int j=1;
   forv(v,s[i]){
     if(!g[j][dd[v]]) g[j][dd[v]]=++it;
     ma[j]=i, mi[j]=(!mi[j])?i:mi[j];
     sz[j]++;
     j=g[j][dd[v]];
   }
   ma[j]=i, mi[j]=(!mi[j])?i:mi[j];
   sz[j]++;
}
ii que(string &x){
   int j=1;
   forv(v,x){
      if(!g[j][dd[v]]) return make_pair(0,0);
      j=g[j][dd[v]];
   }
   return make_pair(mi[j],ma[j]);
}
int get(string &x){
   int j=1;
   forv(v,x){
      if(!g[j][dd[v]]) return 0;
      j=g[j][dd[v]];
   }
   return sz[j];
}

int32_t main(){
   fasty;
   dd['A']=1, dd['G']=2, dd['C']=3, dd['U']=4;
   cin>>n>>m;
   forinc(i,1,n) cin>>s[i];
   forinc(i,1,m) cin>>pf[i]>>sf[i];
   sort(s+1, s+n+1);
   forinc(i,1,n) add(i);
   forinc(i,1,m){
      ii p=que(pf[i]);
      reverse(all(sf[i]));
      if(p.fi) st[p.fi-1].pb(i);
      en[p.se].pb(i);
   }
   it=1;
   reset(g,0); reset(ma,0); reset(mi,0); reset(sz,0);
   forinc(i,1,n){
      reverse(all(s[i]));
      add(i);
      forv(v,st[i]) ans[v]-=get(sf[v]);
      forv(v,en[i]) ans[v]+=get(sf[v]);
   }
   forinc(i,1,m) cout<<ans[i]<<'\n';
}

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