제출 #668267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
668267		Ninja_Kunai	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	1604 ms	541248 KiB

selling_rna

/**
*    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 {
    const int base = 31;
    const int Mod = 1e9 + 7;
    vector <int> Hash[N];
    int Pow[N], ID[N], res[N];
    pair <int, int> q[N];

    struct Fenwick_Tree {
    	vector <int> bit;

    	Fenwick_Tree(int _n = 0) {
    		n = _n;
    		bit.resize(n + 7, 0);
    	}

    	void update(int u, int val) {
    		for (; u <= n; u += u & -u) bit[u] += val;
    	}

    	int get(int u) {
    		int ans = 0;
    		for (; u; u -= u & -u) ans += bit[u];
    		return ans;
    	}

    	int get(int u, int v) {
    		return get(v) - get(u - 1);
    	}
    } mybit;

	struct TRIE_PREF {
		struct node {
			node *child[26];
			int L, R;
 
			node() {
				L = -1, R = -1;
				REP(i, 26) child[i] = NULL;
			}
		} *root;
 
		TRIE_PREF() {
			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;
			}
		}
 
		pair <int, int> get(string &x) {
			node *p = root;
			for (auto c : x) {
				if (p -> child[c - 'A'] == NULL) return make_pair(0, -1);
				p = p -> child[c - 'A'];
			}
 
			return make_pair(p -> L, p -> R);
		}
	} pref;

	struct TRIE_SUFF {
		struct node {
			node *child[26];
			vector <int> q;
 			vector <int> leaf;
 			int numChild;

			node() {
				q.clear();
				leaf.clear();
				numChild = 0;
				REP(i, 26) child[i] = NULL;
			}
		} *root;
 
		TRIE_SUFF() {
			root = new node();
		}
 
		void add(string &x, int ID) {
			node *p = root;
			REP(i, x.size()) {
				char c = x[i];
				if (p -> child[c - 'A'] == NULL) p -> child[c - 'A'] = new node();
				p = p -> child[c - 'A'];
				p -> numChild += x.size() - i;
			}

			p -> leaf.push_back(ID);
			//cout << x << ' ' << ID << '\n';
		}

		void add_query(string &s, int i) {
			node *p = root;
			for (auto c : s) {
				if (p -> child[c - 'A'] == NULL) return;
				p = p -> child[c - 'A'];
			}

			p -> q.push_back(i);
			//cout << i << ' ' << q[i].first << ' ' << q[i].second << '\n';
		}

		void update(int val) {
			for (auto i : root -> leaf) {
				//cout << i << ' ' << val << '\n';
				mybit.update(i, val);
			}

			REP(i, 26) if (root -> child[i] != NULL) {
				node *p = root;
				root = root -> child[i];
				update(val);
				root = p;
			}
		}

		void dfs(bool isClear) {
			node *bigChild = NULL;

			REP(i, 26) if (root -> child[i] != NULL) {
				if (bigChild == NULL || bigChild -> numChild < root -> child[i] -> numChild) {
					bigChild = root -> child[i];
				}
			}

			REP(i, 26) if (root -> child[i] != NULL && root -> child[i] != bigChild) {
				node *p = root;
				root = root -> child[i];
				dfs(1);
				root = p;
			}

			if (bigChild != NULL) {
				node *p = root;
				root = bigChild;
				dfs(0);
				root = p;
			}

			REP(i, 26) if (root -> child[i] != NULL && root -> child[i] != bigChild) {
				node *p = root;
				root = root -> child[i];
				update(1);
				root = p;
			}

			for (auto i : root -> leaf) {
				mybit.update(i, 1);
				//cout << i << ' ' << 1 << '\n';
			}

			for (auto i : root -> q) {
				res[i] = mybit.get(q[i].first, q[i].second);
			}

			if (isClear == 1) {
				//REP(i, 26) if (root -> child[i] != NULL) {
					node *p = root;
					update(-1);
					root = p;
				//}
			}
		}
	} suff;

    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]);
        });
 	
        FOR(i, 1, n) {
        	pref.add(s[ID[i]], i);
        	reverse(ALL(s[ID[i]]));
        	suff.add(s[ID[i]], i);
        }

        mybit = Fenwick_Tree(n);
        FOR(i, 1, nquery) {
        	string PREF, SUFF;
        	cin >> PREF >> SUFF;
        	reverse(ALL(SUFF));
        	q[i] = pref.get(PREF);
        	if (q[i].first <= q[i].second) {
        		suff.add_query(SUFF, i);
        	}
        }

        suff.dfs(0);
        FOR(i, 1, nquery) cout << res[i] << '\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();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}
 
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
 
--------------------------------------------------|
==================================================+
*/

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

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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40