oj.uz

Submission #431339

# Submission time Handle Problem Language Result Execution time Memory
431339 2021-06-17T11:05:52 Z MarcoMeijer Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 232712 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
// mod library
ll MOD=1e9+7;
 
inline ll mod(ll x_) {
    return (x_)%MOD;
}
ll modpow(ll x_, ll N_) {
    if(N_ == 0) return 1;
    ll a = modpow(x_,N_/2);
    a = (a*a)%MOD;
    if(N_%2) a = (a*x_)%MOD;
    return a;
}
ll inv(ll x_) {
    return modpow(x_, MOD-2);
}
class mi {
public:
    mi(ll v=0) {value = v;}
    mi  operator+ (ll rs) {return mod(value+rs);}
    mi  operator- (ll rs) {return mod(value-rs+MOD);}
    mi  operator* (ll rs) {return mod(value*rs);}
    mi  operator/ (ll rs) {return mod(value*inv(rs));}
    mi& operator+=(ll rs) {*this = (*this)+rs; return *this;}
    mi& operator-=(ll rs) {*this = (*this)-rs; return *this;}
    mi& operator*=(ll rs) {*this = (*this)*rs; return *this;}
    mi& operator/=(ll rs) {*this = (*this)/rs; return *this;}
    operator ll&() {return value;}
 
    ll value;
};
typedef vector<mi> vmi;
 
//===================//
//   begin program   //
//===================//
 
const int MX = 2e5;
const int N = (1<<23);
 
// debug
void printString(string s) {
    FOR(c,s) c+='a';
    OUTL(s);
}
 
int n, m;
string s[MX], p[MX], q[MX];
 
// tree
int nodes=1;
vi adj[N];
int w[N];
void createNode(int u) {
    RE(i,4) adj[u].pb(nodes++);
}
 
// trie
string t;
int bg[MX];
int addTrie(int u, int i) {
    if(t.size() == i)
        return u;
    if(adj[u].empty())
        createNode(u);
    return addTrie(adj[u][t[i]],i+1);
}
int getTrie(int u, int i) {
    if(t.size() == i)
        return u;
    if(adj[u].empty())
        return -1;
    return getTrie(adj[u][t[i]],i+1);
}

// 2d problem
int x[MX], y[MX];
int bgx[MX], edx[MX], bgy[MX], edy[MX];
 
void program() {
    // input
    IN(n,m);
    RE(i,n) IN(s[i]);
    RE(i,m) IN(p[i],q[i]);
 
    // compress strings
    map<char,char> charToComp;
    charToComp['A']=0, charToComp['U']=1, charToComp['G']=2, charToComp['C']=3;
    RE(i,n) FOR(c,s[i]) c = charToComp[c];
    RE(i,m) {
        FOR(c,p[i]) c = charToComp[c];
        FOR(c,q[i]) c = charToComp[c];
    }
 
    // create trie
    RE(i,m) reverse(all(q[i]));
    RE(_,2) { // x
        vector<string> v;
        RE(i,n) v.pb(s[i]);
        RE(i,m) v.pb((_?q:p)[i]);
        sort(all(v));

        RE(i,n)
            (_?y:x)[i] = lower_bound(all(v),s[i]) - v.begin();
        
        RE(i,m) {
            (_?bgy:bgx)[i] = lower_bound(all(v),(_?q:p)[i]) - v.begin();
            (_?q:p)[i].back()++;
            (_?edy:edx)[i] = lower_bound(all(v),(_?q:p)[i]) - v.begin() - 1;
            (_?q:p)[i].back()--;
        }

        RE(i,n) reverse(all(s[i]));
    }

    RE(i,m) {
        int cnt = 0;
        RE(j,n) {
            if(bgx[i] <= x[j] && x[j] <= edx[i] && bgy[i] <= y[j] && y[j] <= edy[i])
                cnt++;
        }
        OUTL(cnt);
    }
}

Compilation message

selling_rna.cpp: In function 'int addTrie(int, int)':
selling_rna.cpp:119:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |     if(t.size() == i)
      |        ~~~~~~~~~^~~~
selling_rna.cpp: In function 'int getTrie(int, int)':
selling_rna.cpp:126:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  126 |     if(t.size() == i)
      |        ~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 216072 KB Output is correct
2 Correct 125 ms 216072 KB Output is correct
3 Correct 121 ms 216140 KB Output is correct
4 Correct 128 ms 216236 KB Output is correct
5 Correct 121 ms 216136 KB Output is correct
6 Correct 127 ms 216044 KB Output is correct
7 Correct 121 ms 216128 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 224460 KB Output is correct
2 Correct 339 ms 229060 KB Output is correct
3 Correct 288 ms 228896 KB Output is correct
4 Correct 327 ms 228708 KB Output is correct
5 Correct 272 ms 224148 KB Output is correct
6 Correct 270 ms 224148 KB Output is correct
7 Correct 206 ms 231124 KB Output is correct
8 Correct 311 ms 232712 KB Output is correct
9 Correct 282 ms 232576 KB Output is correct
10 Correct 201 ms 226460 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1607 ms 224420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 216072 KB Output is correct
2 Correct 125 ms 216072 KB Output is correct
3 Correct 121 ms 216140 KB Output is correct
4 Correct 128 ms 216236 KB Output is correct
5 Correct 121 ms 216136 KB Output is correct
6 Correct 127 ms 216044 KB Output is correct
7 Correct 121 ms 216128 KB Output is correct
8 Correct 229 ms 224460 KB Output is correct
9 Correct 339 ms 229060 KB Output is correct
10 Correct 288 ms 228896 KB Output is correct
11 Correct 327 ms 228708 KB Output is correct
12 Correct 272 ms 224148 KB Output is correct
13 Correct 270 ms 224148 KB Output is correct
14 Correct 206 ms 231124 KB Output is correct
15 Correct 311 ms 232712 KB Output is correct
16 Correct 282 ms 232576 KB Output is correct
17 Correct 201 ms 226460 KB Output is correct
18 Execution timed out 1607 ms 224420 KB Time limit exceeded
19 Halted 0 ms 0 KB -