oj.uz

Submission #199429

# Submission time Handle Problem Language Result Execution time Memory
199429 2020-02-01T12:15:17 Z LittleFlowers__ Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 192 ms 85448 KB 
#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";
    }
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 69244 KB Output is correct
2 Correct 40 ms 69240 KB Output is correct
3 Correct 40 ms 69240 KB Output is correct
4 Correct 38 ms 69240 KB Output is correct
5 Correct 39 ms 69240 KB Output is correct
6 Correct 39 ms 69240 KB Output is correct
7 Correct 39 ms 69292 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 81144 KB Output is correct
2 Correct 110 ms 80728 KB Output is correct
3 Correct 122 ms 73592 KB Output is correct
4 Correct 123 ms 73592 KB Output is correct
5 Correct 106 ms 76920 KB Output is correct
6 Correct 114 ms 77048 KB Output is correct
7 Correct 106 ms 75128 KB Output is correct
8 Correct 149 ms 84472 KB Output is correct
9 Correct 135 ms 83832 KB Output is correct
10 Correct 103 ms 78712 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 70392 KB Output is correct
2 Correct 63 ms 70008 KB Output is correct
3 Correct 65 ms 70136 KB Output is correct
4 Correct 60 ms 69880 KB Output is correct
5 Correct 68 ms 69880 KB Output is correct
6 Correct 67 ms 70008 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 69244 KB Output is correct
2 Correct 40 ms 69240 KB Output is correct
3 Correct 40 ms 69240 KB Output is correct
4 Correct 38 ms 69240 KB Output is correct
5 Correct 39 ms 69240 KB Output is correct
6 Correct 39 ms 69240 KB Output is correct
7 Correct 39 ms 69292 KB Output is correct
8 Correct 102 ms 81144 KB Output is correct
9 Correct 110 ms 80728 KB Output is correct
10 Correct 122 ms 73592 KB Output is correct
11 Correct 123 ms 73592 KB Output is correct
12 Correct 106 ms 76920 KB Output is correct
13 Correct 114 ms 77048 KB Output is correct
14 Correct 106 ms 75128 KB Output is correct
15 Correct 149 ms 84472 KB Output is correct
16 Correct 135 ms 83832 KB Output is correct
17 Correct 103 ms 78712 KB Output is correct
18 Correct 66 ms 70392 KB Output is correct
19 Correct 63 ms 70008 KB Output is correct
20 Correct 65 ms 70136 KB Output is correct
21 Correct 60 ms 69880 KB Output is correct
22 Correct 68 ms 69880 KB Output is correct
23 Correct 67 ms 70008 KB Output is correct
24 Correct 124 ms 84344 KB Output is correct
25 Correct 135 ms 85448 KB Output is correct
26 Correct 117 ms 83920 KB Output is correct
27 Correct 140 ms 78076 KB Output is correct
28 Correct 192 ms 81916 KB Output is correct
29 Correct 137 ms 74360 KB Output is correct