oj.uz

Submission #332650

# Submission time Handle Problem Language Result Execution time Memory
332650 2020-12-03T02:20:41 Z Kevin_Zhang_TW Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 420 ms 41928 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &v, T val) { return v < val ? (v = val, true) : false; }
template<class T>
bool chmin(T &v, T val) { return val < v ? (v = val, true) : false; }

#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 100010, SQRT = 320;

int n, m, enc[256], res[MAX_N];
string w[MAX_N], p[MAX_N], q[MAX_N], rw[MAX_N];
int ac[MAX_N], ca[MAX_N];

struct ask {
	int u, d, sc, id;
	ask(int u, int d, int sc, int id) :
		u(u), d(d), sc(sc), id(id) {}
	ask() {};
	bool operator < (ask b) { return d < b.d; }
};
vector<ask> allq[ SQRT ];
//bitset<5000> pfa[MAX_N], pfb[MAX_N];
void brute(const vector<ask> &qries) {
//	for (int i = 0;i < n;++i) {
//		if (i) pfa[i] = pfa[i-1];
//		pfa[i][ ac[i] ] = true;
//	}
//	for (int i = 0;i < n;++i) {
//		if (i) pfb[i] = pfb[i-1];
//		pfb[i][ ca[i] ] = true;
//	}

	for (auto [u, d, sc, id] : qries) {
		if (min(u, d) < 0) continue;
		allq[ u / SQRT ].pb(u, d, sc, id);
	}

	vector<int> cnta(n), cntb(n);
	int cu = -1, cd = -1, sum = 0;
	auto puta = [&](int id, int sc) {
		sum -= cnta[id] && cntb[id];
		cnta[id] += sc;
		sum += cnta[id] && cntb[id];
	};
	auto putb = [&](int id, int sc) {
		sum -= cnta[id] && cntb[id];
		cntb[id] += sc;
		sum += cnta[id] && cntb[id];
	};
	for (int i = 0;i < SQRT;++i) if (allq[i].size()) {
		sort(AI(allq[i]));
		for (auto [u, d, sc, id] : allq[i]) {
//		res[id] += sc * (pfa[u] & pfb[d]).count();
//		continue;
			while (cu < u) puta(ac[++cu], 1);
			while (cu > u) puta(ac[cu--], -1);
			while (cd < d) putb(ca[++cd], 1);
			while (cd > d) putb(ca[cd--], -1);
			res[id] += sc * sum;
			DE(u, d, cu, cd);
		}
	}
}
bool cmpac(int a, int b) { return w[a] < w[b]; }
bool cmpca(int a, int b) { return rw[a] < rw[b]; }

void solve() {
	iota(ac, ac+n, 0);
	iota(ca, ca+n, 0);
	for (int i = 0;i < n;++i) {
		rw[i] = w[i];
		reverse(AI(rw[i]));
	}
	for (int i = 0;i < m;++i)
		reverse(AI(q[i]));

	sort(ca, ca+n, cmpca);
	
	vector<ask> qries;

	for (int i = 0;i < m;++i) {
		w[n] = p[i];
		rw[n] = q[i];

		int al = lower_bound(ac, ac+n, n, cmpac) - ac;
		int cl = lower_bound(ca, ca+n, n, cmpca) - ca;
		w[n].push_back(255);
		rw[n].push_back(255);
		int ar = lower_bound(ac, ac+n, n, cmpac) - ac;
		int cr = lower_bound(ca, ca+n, n, cmpca) - ca;
		DE(al, ar, cl, cr);
		if (al == ar || cl == cr) continue;
		--ar, --cr;

		qries.pb(ar, cr, 1, i), qries.pb(ar, cl-1, -1, i);
		qries.pb(al-1, cr, -1, i), qries.pb(al-1, cl-1, 1, i);
	}

	brute(qries);
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	enc['A'] = 0, enc['G'] = 1, enc['C'] = 2, enc['U'] = 3;
	cin >> n >> m;
	for (int i = 0;i < n;++i)
		cin >> w[i];

	for (int i = 0;i < m;++i)
		cin >> p[i] >> q[i];

	sort(w, w+n);


	solve();

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

Compilation message

selling_rna.cpp: In function 'void brute(const std::vector<ask>&)':
selling_rna.cpp:19:17: warning: statement has no effect [-Wunused-value]
   19 | #define DE(...) 0
      |                 ^
selling_rna.cpp:75:4: note: in expansion of macro 'DE'
   75 |    DE(u, d, cu, cd);
      |    ^~
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:19:17: warning: statement has no effect [-Wunused-value]
   19 | #define DE(...) 0
      |                 ^
selling_rna.cpp:106:3: note: in expansion of macro 'DE'
  106 |   DE(al, ar, cl, cr);
      |   ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19436 KB Output is correct
2 Correct 50 ms 19812 KB Output is correct
3 Correct 47 ms 19940 KB Output is correct
4 Correct 49 ms 19940 KB Output is correct
5 Correct 39 ms 17772 KB Output is correct
6 Correct 39 ms 17764 KB Output is correct
7 Correct 44 ms 21112 KB Output is correct
8 Correct 57 ms 21992 KB Output is correct
9 Correct 53 ms 21992 KB Output is correct
10 Correct 35 ms 19308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 20576 KB Output is correct
2 Correct 76 ms 18788 KB Output is correct
3 Correct 90 ms 19424 KB Output is correct
4 Correct 67 ms 18656 KB Output is correct
5 Correct 86 ms 18148 KB Output is correct
6 Correct 116 ms 19680 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 9 ms 12908 KB Output is correct
7 Correct 9 ms 12908 KB Output is correct
8 Correct 31 ms 19436 KB Output is correct
9 Correct 50 ms 19812 KB Output is correct
10 Correct 47 ms 19940 KB Output is correct
11 Correct 49 ms 19940 KB Output is correct
12 Correct 39 ms 17772 KB Output is correct
13 Correct 39 ms 17764 KB Output is correct
14 Correct 44 ms 21112 KB Output is correct
15 Correct 57 ms 21992 KB Output is correct
16 Correct 53 ms 21992 KB Output is correct
17 Correct 35 ms 19308 KB Output is correct
18 Correct 86 ms 20576 KB Output is correct
19 Correct 76 ms 18788 KB Output is correct
20 Correct 90 ms 19424 KB Output is correct
21 Correct 67 ms 18656 KB Output is correct
22 Correct 86 ms 18148 KB Output is correct
23 Correct 116 ms 19680 KB Output is correct
24 Correct 116 ms 26448 KB Output is correct
25 Correct 211 ms 31580 KB Output is correct
26 Correct 88 ms 24808 KB Output is correct
27 Correct 108 ms 26592 KB Output is correct
28 Correct 420 ms 41928 KB Output is correct
29 Correct 276 ms 32208 KB Output is correct