oj.uz

Submission #199427

# Submission time Handle Problem Language Result Execution time Memory
199427 2020-02-01T12:10:21 Z LittleFlowers__ Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 188 ms 153464 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);
    }

    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 42 ms 69244 KB Output is correct
2 Correct 38 ms 69240 KB Output is correct
3 Correct 39 ms 69240 KB Output is correct
4 Correct 42 ms 69244 KB Output is correct
5 Correct 40 ms 69240 KB Output is correct
6 Correct 39 ms 69240 KB Output is correct
7 Correct 40 ms 69240 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 81120 KB Output is correct
2 Correct 115 ms 80760 KB Output is correct
3 Correct 127 ms 73468 KB Output is correct
4 Correct 124 ms 73436 KB Output is correct
5 Runtime error 188 ms 153464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 70264 KB Output is correct
2 Correct 60 ms 70008 KB Output is correct
3 Correct 64 ms 70136 KB Output is correct
4 Correct 61 ms 69880 KB Output is correct
5 Correct 61 ms 70008 KB Output is correct
6 Correct 69 ms 70008 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 69244 KB Output is correct
2 Correct 38 ms 69240 KB Output is correct
3 Correct 39 ms 69240 KB Output is correct
4 Correct 42 ms 69244 KB Output is correct
5 Correct 40 ms 69240 KB Output is correct
6 Correct 39 ms 69240 KB Output is correct
7 Correct 40 ms 69240 KB Output is correct
8 Correct 109 ms 81120 KB Output is correct
9 Correct 115 ms 80760 KB Output is correct
10 Correct 127 ms 73468 KB Output is correct
11 Correct 124 ms 73436 KB Output is correct
12 Runtime error 188 ms 153464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -