답안 #98309 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98309	2019-02-22T02:34:22 Z	qkxwsm	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1422 ms	237080 KB

selling_rna

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

random_device(rd);
mt19937 rng(rd());
const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

struct custom_hash
{
	template<class T>
	unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x += FIXED_RANDOM;
		// x += 11400714819323198485ull;
		// x = (x ^ (x >> 30)) * 13787848793156543929ull;
		x = (x ^ (x >> 27)) * 10723151780598845931ull;
		return x ^ (x >> 31);
	}
};

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;

template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}
template<class T>
void readi(T &x)
{
	x = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		x = -x;
	}
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int buf[20], n = 0;
	while(output)
	{
		buf[n] = ((output % 10));
		output /= 10;
		n++;
	}
	for (n--; n >= 0; n--)
	{
		putchar(buf[n] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long expo(long long a, long long e, long long mod)
{
	return ((e == 0) ? 1 : ((expo(a * a % mod, e >> 1, mod)) * ((e & 1) ? a : 1) % mod));
}
template<class T, class U>
void nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define SZ(x) ((int) ((x).size()))
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-9;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 500013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<pii, pii> ppp;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pdd> vpd;

int N, Q;
pair<vi, pii> s[MAXN];
vpl sh[MAXN], th[MAXN];
pair<vi, vi> t[MAXN];
ppp rect[MAXN];
int ans[MAXN];
vector<ppp> ask[MAXN];

bool cmp(pair<vi, pii> a, pair<vi, pii> b)
{
	return a.se.fi < b.se.fi;
}
int mpc(char c)
{
	if (c == 'A') return 1;
	if (c == 'C') return 2;
	if (c == 'G') return 3;
	if (c == 'U') return 4;
}
int compare(int x, int y, bool flag)
{
	//compare s[x] with t[y]
	int lo = 0, hi = min(SZ(s[x].fi), (flag ? SZ(t[y].se) : SZ(t[y].fi)));
	while(hi > lo)
	{
		int mid = (hi + lo + 1) >> 1;
		if (sh[x][mid] == th[y][mid])
		{
			lo = mid;
		}
		else
		{
			hi = mid - 1;
		}
	}
	int res;
	if (lo == (flag ? SZ(t[y].se) : SZ(t[y].fi))) res = 0;
	else res = ((lo == SZ(s[x].fi) || s[x].fi[lo] < (flag ? t[y].se[lo] : t[y].fi[lo])) ? -1 : 1);
	// cerr << "ask " << x << ' ' << y << ' ' << res << endl;
	return res;
}

int fen[MAXN];

void upd(int idx, int v)
{
	for (int e = idx + 1; e <= N; e += e & (-e))
	{
		fen[e] += v;
	}
}
int query(int idx)
{
	int res = 0;
	for (int e = idx + 1; e; e -= e & (-e))
	{
		res += fen[e];
	}
	return res;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	// cout << fixed << setprecision(10);
	// cerr << fixed << setprecision(10);
	// if (fopen("file.in", "r"))
	// {
	// 	freopen ("file.in", "r", stdin);
	// 	freopen ("file.out", "w", stdout);
	// }
	cin >> N >> Q;
	FOR(i, 0, N)
	{
		string temps;
		cin >> temps;
		for(char c : temps)
		{
			s[i].fi.PB(mpc(c));
		}
	}
	FOR(i, 0, Q)
	{
		string temps, tempt;
		cin >> temps >> tempt;
		// DBG(temps); DBG(tempt);
		t[i].fi.clear();
		for (char c : temps)
		{
			t[i].fi.PB(mpc(c));
		}
		for (char c : tempt)
		{
			t[i].se.PB(mpc(c));
		}
	}
	sort(s, s + N);
	FOR(i, 0, N)
	{
		s[i].se.fi = i;
	}
	FOR(i, 0, N)
	{
		sh[i].clear();
		sh[i].PB({0, 0});
		for (int x : s[i].fi)
		{
			pll p = sh[i].back();
			p.fi *= CO; p.fi += x; p.fi %= INF;
			p.se *= CO; p.se += x; p.se %= BIG;
			sh[i].PB(p);
		}
	}
	FOR(i, 0, Q)
	{
		th[i].PB({0, 0});
		for (int x : t[i].fi)
		{
			pll p = th[i].back();
			p.fi *= CO; p.fi += x; p.fi %= INF;
			p.se *= CO; p.se += x; p.se %= BIG;
			th[i].PB(p);
		}
		int lo = 0, hi = N;
		while(hi > lo)
		{
			int mid = (hi + lo) >> 1;
			if (compare(mid, i, 0) == -1) //mid < i
			{
				lo = mid + 1;
			}
			else
			{
				hi = mid;
			}
		}
		rect[i].fi.fi = lo;
		lo = -1; hi = N - 1;
		while(hi > lo)
		{
			int mid = (hi + lo + 1) >> 1;
			if (compare(mid, i, 0) == 1)
			{
				hi = mid - 1;
			}
			else
			{
				lo = mid;
			}
		}
		rect[i].fi.se = lo;
	}
	FOR(i, 0, N)
	{
		reverse(ALL(s[i].fi));
	}
	sort(s, s + N);
	FOR(i, 0, N)
	{
		s[i].se.se = i;
	}
	FOR(i, 0, N)
	{
		sh[i].clear();
		sh[i].PB({0, 0});
		for (int x : s[i].fi)
		{
			pll p = sh[i].back();
			p.fi *= CO; p.fi += x; p.fi %= INF;
			p.se *= CO; p.se += x; p.se %= BIG;
			sh[i].PB(p);
		}
	}
	// FOR(i, 0, N)
	// {
	// 	cerr << s[i].se.fi << ',' << s[i].se.se << endl;
	// }
	FOR(i, 0, Q)
	{
		reverse(ALL(t[i].se));
		th[i].clear();
		th[i].PB({0, 0});
		for (int x : t[i].se)
		{
			pll p = th[i].back();
			p.fi *= CO; p.fi += x; p.fi %= INF;
			p.se *= CO; p.se += x; p.se %= BIG;
			th[i].PB(p);
		}
		int lo = 0, hi = N;
		while(hi > lo)
		{
			int mid = (hi + lo) >> 1;
			if (compare(mid, i, 1) == -1) //mid < i
			{
				lo = mid + 1;
			}
			else
			{
				hi = mid;
			}
		}
		rect[i].se.fi = lo;
		lo = -1; hi = N - 1;
		while(hi > lo)
		{
			int mid = (hi + lo + 1) >> 1;
			if (compare(mid, i, 1) == 1)
			{
				hi = mid - 1;
			}
			else
			{
				lo = mid;
			}
		}
		rect[i].se.se = lo;
		// cerr << rect[i].fi.fi << ',' << rect[i].fi.se << " && " << rect[i].se.fi << ',' << rect[i].se.se << endl;
	}
	sort(s, s + N, cmp);
	FOR(i, 0, Q)
	{
		if (rect[i].fi.fi > rect[i].fi.se || rect[i].se.fi > rect[i].se.se)
		{
			continue;
		}
		ask[rect[i].fi.se].PB({{1, i}, {rect[i].se.fi, rect[i].se.se}});
		if (rect[i].fi.fi) ask[rect[i].fi.fi - 1].PB({{-1, i}, {rect[i].se.fi, rect[i].se.se}});
	}
	FOR(i, 0, N)
	{
		// cerr << "update " << s[i].se.se << endl;
		upd(s[i].se.se, 1);
		for (ppp x : ask[i])
		{
			// cerr << "help " << x.fi.se << ' ' << x.fi.fi * (query(x.se.se) - query(x.se.fi - 1)) << endl;
			ans[x.fi.se] += x.fi.fi * (query(x.se.se) - query(x.se.fi - 1));
		}
	}
	// FOR(i, 0, Q)
	// {
	// 	FOR(j, 0, N)
	// 	{
	// 		if (rect[i].fi.fi <= s[j].se.fi && s[j].se.fi <= rect[i].fi.se && rect[i].se.fi <= s[j].se.se && s[j].se.se <= rect[i].se.se)
	// 		{
	// 			ans[i]++;
	// 		}
	// 	}
	// }
	FOR(i, 0, Q)
	{
		cout << ans[i] << '\n';
	}
	// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}
/* READ READ READ
* int overflow, maxn too small, special cases (n=1?, two distinct?), cin.tie() interactive
* reread the problem, try small cases
* note down possible sources of error as you go
* do smth instead of nothing
*/

Compilation message

selling_rna.cpp: In function 'int mpc(char)':
selling_rna.cpp:172:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	74748 KB	Output is correct
2	Correct	77 ms	74744 KB	Output is correct
3	Correct	76 ms	74744 KB	Output is correct
4	Correct	77 ms	74872 KB	Output is correct
5	Correct	85 ms	74804 KB	Output is correct
6	Correct	70 ms	74872 KB	Output is correct
7	Correct	75 ms	74744 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	377 ms	190572 KB	Output is correct
2	Correct	441 ms	200608 KB	Output is correct
3	Correct	468 ms	197844 KB	Output is correct
4	Correct	463 ms	201080 KB	Output is correct
5	Correct	358 ms	142948 KB	Output is correct
6	Correct	365 ms	143240 KB	Output is correct
7	Correct	424 ms	193012 KB	Output is correct
8	Correct	545 ms	185728 KB	Output is correct
9	Correct	586 ms	185860 KB	Output is correct
10	Correct	420 ms	154744 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	350 ms	90460 KB	Output is correct
2	Correct	259 ms	88284 KB	Output is correct
3	Correct	262 ms	89692 KB	Output is correct
4	Correct	264 ms	85664 KB	Output is correct
5	Correct	268 ms	88056 KB	Output is correct
6	Correct	285 ms	90104 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	74748 KB	Output is correct
2	Correct	77 ms	74744 KB	Output is correct
3	Correct	76 ms	74744 KB	Output is correct
4	Correct	77 ms	74872 KB	Output is correct
5	Correct	85 ms	74804 KB	Output is correct
6	Correct	70 ms	74872 KB	Output is correct
7	Correct	75 ms	74744 KB	Output is correct
8	Correct	377 ms	190572 KB	Output is correct
9	Correct	441 ms	200608 KB	Output is correct
10	Correct	468 ms	197844 KB	Output is correct
11	Correct	463 ms	201080 KB	Output is correct
12	Correct	358 ms	142948 KB	Output is correct
13	Correct	365 ms	143240 KB	Output is correct
14	Correct	424 ms	193012 KB	Output is correct
15	Correct	545 ms	185728 KB	Output is correct
16	Correct	586 ms	185860 KB	Output is correct
17	Correct	420 ms	154744 KB	Output is correct
18	Correct	350 ms	90460 KB	Output is correct
19	Correct	259 ms	88284 KB	Output is correct
20	Correct	262 ms	89692 KB	Output is correct
21	Correct	264 ms	85664 KB	Output is correct
22	Correct	268 ms	88056 KB	Output is correct
23	Correct	285 ms	90104 KB	Output is correct
24	Correct	572 ms	215416 KB	Output is correct
25	Correct	672 ms	221396 KB	Output is correct
26	Correct	588 ms	213396 KB	Output is correct
27	Correct	692 ms	215220 KB	Output is correct
28	Correct	1387 ms	237080 KB	Output is correct
29	Correct	1422 ms	161604 KB	Output is correct

답안 #98309

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0