oj.uz

Submission #668202

# Submission time Handle Problem Language Result Execution time Memory
668202 2022-12-03T08:56:05 Z Ninja_Kunai Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 531 ms 638984 KB 
/**
*    Author :  Nguyen Tuan Vu
*    Created : 02.12.2022
**/
 
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
 
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}
 
using namespace std;
 
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}
 
void file(){
    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}
 
const int N = 1e5 + 5;
int n, nquery;
string s[N];
 
//namespace sub4 {
    struct TRIE {
        struct node {
            node *child[26];
            int L, R, dd;
            vector <int> S;
 
            node() {
                S.clear();
                L = -1, R = -1;
                dd = 0;
                REP(i, 26) child[i] = NULL;
            }
        } *root;
 
        TRIE() {
            root = new node();
        }
 
        void add(string &x, int ID) {
            node *p = root;
            for (auto c : x) {
                if (p -> child[c - 'A'] == NULL) p -> child[c - 'A'] = new node();
                p = p -> child[c - 'A'];
                if (p -> L == -1) p -> L = p -> R = ID;
                else p -> R = ID;

                if (p -> dd == 1) {
                    p -> S.push_back(ID);
                }
            }
        }
 
        pair <int, int> get(string &x) {
            node *p = root;
            for (auto c : x) {
                if (p -> child[c - 'A'] == NULL) return make_pair(-1, 0);
                p = p -> child[c - 'A'];
            }
 
            return make_pair(p -> L, p -> R);
        }
 
        int get(string &x, int L, int R) {
            node *p = root;
            for (auto c : x) {
                if (p -> child[c - 'A'] == NULL) return 0;
                p = p -> child[c - 'A'];
            }
    
            int ans = 0;
            for (auto x : p -> S) if (L <= x && x <= R) ++ans;
            return ans;
        }        

       	void mark(string &x) {
       		node *p = root;
       		for (auto c : x) {
       			if (p -> child[c - 'A'] == NULL) return;
       			p = p -> child[c - 'A'];
       		}

       		p -> dd = 1;
       	}
    } pref, suff;
 
    const int base = 31;
    const int Mod = 1e9 + 7;
    pair <string, string> q[N];
    vector <int> Hash[N];
    int Pow[N], ID[N];
 
    int getHash(int i, int l, int r) {
        return (Hash[i][r] - 1ll * Hash[i][l - 1] * Pow[r - l + 1] % Mod + Mod) % Mod;
    }
 
    void solve() {
        FOR(i, 1, n) {
            Hash[i].resize(s[i].size() + 5, 0);
            REP(j, s[i].size()) Hash[i][j + 1] = (1ll * Hash[i][j] * base % Mod + s[i][j] - 'A' + 1) % Mod;
        }
 
        Pow[0] = 1;
        FOR(i, 1, 1e5) Pow[i] = 1ll * Pow[i - 1] * base % Mod;
        FOR(i, 1, n) ID[i] = i;
        sort (ID + 1, ID + n + 1, [] (int &x, int &y) {
            int l = 0, r = min((int) s[x].size(), (int) s[y].size()) + 1;
            while (r - l > 1) {
                int mid = (l + r) >> 1;
                if (getHash(x, 1, mid) == getHash(y, 1, mid)) l = mid;
                else r = mid;
            }
 
            if (l == min((int) s[x].size(), (int) s[y].size())) {
                return (s[x].size() <= s[y].size());
            }
 
            return (s[x][l] <= s[y][l]);
        });
 
        //if (n > 100 || nquery > 100) return;
        FOR(i, 1, n) {
            pref.add(s[ID[i]], i);
            reverse(ALL(s[ID[i]]));
            suff.add(s[ID[i]], i);
        }
 	
        FOR(i, 1, nquery) {
        	cin >> q[i].first >> q[i].second;
        	reverse(ALL(q[i].second));
        	suff.mark(q[i].second);
        }

        FOR(i, 1, n) suff.add(s[ID[i]], i);
        FOR(i, 1, nquery) {
            pair <int, int> Pref = pref.get(q[i].first);
            int Suff = suff.get(q[i].second, Pref.first, Pref.second);
            cout << Suff << '\n';
        }
    }
//}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    file();
 
    cin >> n >> nquery;
    FOR(i, 1, n) cin >> s[i];
    //sub4::solve();
    solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}
 
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
*/

Compilation message

selling_rna.cpp: In function 'void file()':
selling_rna.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Correct 7 ms 12500 KB Output is correct
4 Correct 9 ms 12500 KB Output is correct
5 Correct 8 ms 12500 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 7 ms 12500 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 518288 KB Output is correct
2 Correct 421 ms 491824 KB Output is correct
3 Correct 340 ms 519668 KB Output is correct
4 Correct 326 ms 497628 KB Output is correct
5 Correct 531 ms 629584 KB Output is correct
6 Correct 518 ms 638984 KB Output is correct
7 Correct 94 ms 32036 KB Output is correct
8 Correct 364 ms 384252 KB Output is correct
9 Correct 312 ms 326284 KB Output is correct
10 Correct 239 ms 317940 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 30164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 7 ms 12500 KB Output is correct
3 Correct 7 ms 12500 KB Output is correct
4 Correct 9 ms 12500 KB Output is correct
5 Correct 8 ms 12500 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 7 ms 12500 KB Output is correct
8 Correct 425 ms 518288 KB Output is correct
9 Correct 421 ms 491824 KB Output is correct
10 Correct 340 ms 519668 KB Output is correct
11 Correct 326 ms 497628 KB Output is correct
12 Correct 531 ms 629584 KB Output is correct
13 Correct 518 ms 638984 KB Output is correct
14 Correct 94 ms 32036 KB Output is correct
15 Correct 364 ms 384252 KB Output is correct
16 Correct 312 ms 326284 KB Output is correct
17 Correct 239 ms 317940 KB Output is correct
18 Runtime error 28 ms 30164 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -