oj.uz

Submission #332649

# Submission time Handle Problem Language Result Execution time Memory
332649 2020-12-03T02:20:20 Z Kevin_Zhang_TW Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 55 ms 22120 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);

	if (n > 5000) return 1;

	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 10 ms 12908 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 19436 KB Output is correct
2 Correct 49 ms 19940 KB Output is correct
3 Correct 47 ms 20068 KB Output is correct
4 Correct 50 ms 20068 KB Output is correct
5 Correct 39 ms 17900 KB Output is correct
6 Correct 40 ms 17892 KB Output is correct
7 Correct 44 ms 21220 KB Output is correct
8 Correct 55 ms 22120 KB Output is correct
9 Correct 54 ms 22120 KB Output is correct
10 Correct 36 ms 19436 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 12908 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
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 10 ms 12908 KB Output is correct
8 Correct 32 ms 19436 KB Output is correct
9 Correct 49 ms 19940 KB Output is correct
10 Correct 47 ms 20068 KB Output is correct
11 Correct 50 ms 20068 KB Output is correct
12 Correct 39 ms 17900 KB Output is correct
13 Correct 40 ms 17892 KB Output is correct
14 Correct 44 ms 21220 KB Output is correct
15 Correct 55 ms 22120 KB Output is correct
16 Correct 54 ms 22120 KB Output is correct
17 Correct 36 ms 19436 KB Output is correct
18 Runtime error 25 ms 12908 KB Execution failed because the return code was nonzero
19 Halted 0 ms 0 KB -