제출 #199429

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

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#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 fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=100010;

int n,m;
int ans[N];
string s[N],pf[N],sf[N];
vector<int> st[N],ed[N];

int it=1;
int mx[2000010],mn[2000010],sz[2000010];
int nxt[2000010][5];

int mode;

void norm(string &s){
    forv(i,s) i=i=='U'?'B':i=='G'?'D':i;
}

void add(int t){
    int i=1;
    forv(j,s[t]){
        if(!nxt[i][j-'A']) nxt[i][j-'A']=++it;
        mx[i]=t; mn[i]=mn[i]?mn[i]:t; if(mode) sz[i]++;
        i=nxt[i][j-'A'];
    }
    mx[i]=t; mn[i]=mn[i]?mn[i]:t; if(mode) sz[i]++;
}

ii que(const string&s){
    int i=1;
    forv(j,s){
        if(!nxt[i][j-'A']) return {0,0};
        i=nxt[i][j-'A'];
    }
    return {mode?sz[i]:mn[i],mx[i]};
}

main(){
    #define task "RNA"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    fasty;
    cin>>n>>m;
    forinc(i,1,n){
        cin>>s[i];
        norm(s[i]);
    }
    sort(s+1,s+n+1);
    forinc(i,1,n) add(i);
    forinc(i,1,m){
        cin>>pf[i]>>sf[i];
        norm(pf[i]), norm(sf[i]);
        reverse(all(sf[i]));
        ii j=que(pf[i]);
        if(j.fi) st[j.fi-1].pb(i);
        ed[j.se].pb(i);
    }

    it=1;
    reset(mx,0);
    reset(mn,0);
    reset(nxt,0);

    mode=1;

    forinc(i,1,n){
        reverse(all(s[i]));
        add(i);
        forv(j,st[i]) ans[j]-=que(sf[j]).fi;
        forv(j,ed[i]) ans[j]+=que(sf[j]).fi;
    }
    forinc(i,1,m){
        cout<<ans[i]<<"\n";
    }
}

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

selling_rna.cpp:58:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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