Submission #1271729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271729		thieunguyenhuy	Selling RNA Strands (JOI16_selling_rna)	C++20	10 / 100	1597 ms	36700 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);
}
unsigned long long random(unsigned long long l, unsigned long long r) {
    return uniform_int_distribution<unsigned long long>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 1e5 + 5;
const int inf = 1e9;
const long long INF = 1e18;

const int base = 311;
const int MOD = 1e9 + 7;

template <const int MOD = int(1e9) + 7>
struct Modular {
    int value;

    Modular(ll x = 0) {
        if (-MOD <= x && x < 2 * MOD) {
            value = x;
            if (value >= MOD) value -= MOD;
            if (value < 0) value += MOD;
        }
        else {
            value = x % MOD;
            if (value < 0) value += MOD;
        }
    }

    friend istream& operator >> (istream &is, Modular &x) {
        return is >> x.value;
    }

    friend ostream& operator << (ostream &os, Modular x) {
        return os << x.value;
    }

    void operator = (ll x) {
        *this = Modular(x);
    }

    void operator += (Modular x) {
        value += x.value;
        if (value >= MOD) value -= MOD;
    }
    void operator += (ll x) {
        *this += Modular(x);
    }
    Modular operator + (Modular x) {
        Modular res = *this; res += x;
        return res; 
    }
    Modular operator + (ll x) {
        return *this + Modular(x);
    };
    friend Modular operator + (ll x, Modular y){
        return y + x;
    }

    void operator -= (Modular x) {
        value -= x.value;
        if (value < 0) value += MOD;
    }
    void operator -= (ll x) {
        *this -= Modular(x);
    }
    Modular operator - (Modular x) {
        Modular res = *this; res -= x;
        return res;
    }
    Modular operator - (ll x) {
        return *this - Modular(x);
    }
    friend Modular operator - (ll x, Modular y) {
        return Modular(x) - y;
    }

    void operator *= (Modular x) {
        value = 1ll * value * x.value % MOD;
    }
    void operator *= (ll x) {
        *this *= Modular(x);
    }
    Modular operator * (Modular x) {
        Modular res = *this; res *= x;
        return res;
    }
    Modular operator * (ll x) {
        return *this * Modular(x);
    }
    friend Modular operator * (ll x, Modular y) {
        return y * x;
    }

    void operator /= (Modular x) {
        *this *= x.inverse();
    }
    void operator /= (ll x) {
        *this *= Modular(x).inverse();
    }
    Modular operator / (Modular x) {
        Modular res = *this; res /= x;
        return res;
    }
    Modular operator / (ll x) {
        return *this / Modular(x);
    }
    friend Modular operator / (ll x, Modular y) {
        return x * y.inverse();
    }

    Modular binpow(ll n) {
        Modular res(1), mul = *this;
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul, n >>= 1;
        }
        return res;
    }

    Modular binpow(Modular x) {
       return binpow(x.value);
    }

    Modular inverse() {
        return binpow(MOD - 2);
    }

    bool operator == (Modular x) {
    	return value == x.value;
    }

    bool operator != (Modular x) {
    	return value != x.value;
    }
};
using ModInt = Modular<MOD>;

int n, m;
int ans[N];

struct Hash {
	string s;
	vector<ModInt> hash;

	Hash() {}

	Hash(const string &S) {
		s = S; hash.assign(s.size(), 0);
		hash[0] = s[0];
		for (int i = 1; i < s.size(); ++i)
			hash[i] = hash[i - 1] * base + s[i];
	}

	int size() {
		return s.size();
	}

	ModInt get(int p) {
		if (p >= hash.size()) return MOD;
		return hash[p];
	}
};

bool isLess(Hash hashA, Hash hashB) { // return true if A < B
	int differ = min(hashA.size(), hashB.size());
	int low = 0, high = differ - 1;
	while (low <= high) {
		int mid = (low + high) >> 1;
		if (hashA.get(mid) != hashB.get(mid)) high = (differ = mid) - 1;
		else low = mid + 1;
	}

	if (differ < hashA.size() && differ < hashB.size())
		return hashA.s[differ] < hashB.s[differ];
	return differ < hashB.size();
}

pii find(vector<Hash> hash, Hash hashP) {
	int low = 0, high = n - 1, L = -1;
	while (low <= high) {
		int mid = (low + high) >> 1;
		if (isLess(hash[mid], hashP)) low = mid + 1;
		else high = (L = mid) - 1;
	}
	if (L == -1) return make_pair(-1, -1);

	// cerr << "L = " << L << '\n';

	ModInt allP = hashP.get(hashP.size() - 1);
	if (hash[L].get(hashP.size() - 1) != allP) return make_pair(-1, -1);

	low = L, high = n - 1; int R = -1;
	while (low <= high) {
		int mid = (low + high) >> 1;
		if (hash[mid].get(hashP.size() - 1) == allP) 
			low = (R = mid) + 1;
		else high = mid - 1;
	}
	assert(R != -1);

	return make_pair(L, R);
}

struct Query {
	int l, r, id;

	Query(int _l = 0, int _r = 0, int _id = 0) {
		l = _l, r = _r, id = _id;
	}
};
vector<Query> que[N];

struct FenwickTree {
    using T = int;
    vector<T> bit;

    FenwickTree() {}

    void resize(int n) {
        bit.assign(n + 1, 0);
    }

    void update(int p, T val) {
    	++p;
        for (; p < int(bit.size()); p += p & -p) bit[p] += val;
    }

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

    T get(int l, int r) {
    	return get(r) - get(l - 1);
    }
} fen;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

	vector<string> s(n);
	for (auto &x : s) cin >> x;

	sort (s.begin(), s.end());

	vector<pair<string, int>> tmp(n);
	for (int i = 0; i < n; ++i) {
		tmp[i] = make_pair(s[i], i);
		reverse(tmp[i].fi.begin(), tmp[i].fi.end());
	}
	sort (tmp.begin(), tmp.end());

	vector<string> t(n);
	for (int i = 0; i < n; ++i) {
		t[i] = tmp[i].fi;
	}

	vector<Hash> hashS(n), hashT(n);
	for (int i = 0; i < n; ++i) {
		hashS[i] = Hash(s[i]);
		hashT[i] = Hash(t[i]);
	}

	for (int i = 1; i <= m; ++i) {
		string p, q; cin >> p >> q;
		reverse(q.begin(), q.end());
		Hash hashP(p), hashQ(q);
		auto [l1, r1] = find(hashS, hashP);
		auto [l2, r2] = find(hashT, hashQ);
		if (l1 == -1 || l2 == -1) {
			ans[i] = 0;
			continue;
		}
		que[r2].emplace_back(l1, r1, i);
		if (l2 > 0) que[l2 - 1].emplace_back(l1, r1, -i);
		// cerr << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
	}

	fen.resize(n);
	for (int r2 = 0; r2 < n; ++r2) {
		fen.update(tmp[r2].se, 1);
		for (auto [l, r, id] : que[r2]) {
			int sign = (id > 0) - (id < 0);
			ans[abs(id)] += sign * fen.get(l, r);
		}
	}

	for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40