oj.uz

Submission #332638

# Submission time Handle Problem Language Result Execution time Memory
332638 2020-12-03T01:59:37 Z Kevin_Zhang_TW Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 74 ms 28648 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;

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) {}

};
bitset<5000> pfa[MAX_N], pfb[MAX_N];
void brute(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;
		DE(u, d, sc, id);
		res[id] += sc * (pfa[u] & pfb[d]).count();
	}
}
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);
//
//	for (int i = 0;i < n;++i) 
//		cout << w[ ac[i] ] << '\n';
//	cout << '\n';
//	for (int i = 0;i < n;++i) 
//		cout << w[ ca[i] ] << '\n';

	
	vector<ask> qries;

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

		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(std::vector<ask>)':
selling_rna.cpp:19:17: warning: statement has no effect [-Wunused-value]
   19 | #define DE(...) 0
      |                 ^
selling_rna.cpp:47:3: note: in expansion of macro 'DE'
   47 |   DE(u, d, sc, id);
      |   ^~
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:77:3: note: in expansion of macro 'DE'
   77 |   DE(w[n], rw[n]);
      |   ^~
selling_rna.cpp:19:17: warning: statement has no effect [-Wunused-value]
   19 | #define DE(...) 0
      |                 ^
selling_rna.cpp:85:3: note: in expansion of macro 'DE'
   85 |   DE(al, ar, cl, cr);
      |   ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 22380 KB Output is correct
2 Correct 53 ms 26596 KB Output is correct
3 Correct 50 ms 24292 KB Output is correct
4 Correct 56 ms 26596 KB Output is correct
5 Correct 52 ms 24428 KB Output is correct
6 Correct 49 ms 24420 KB Output is correct
7 Correct 50 ms 23524 KB Output is correct
8 Correct 74 ms 28648 KB Output is correct
9 Correct 68 ms 28640 KB Output is correct
10 Correct 46 ms 26216 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 13164 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 10 ms 13036 KB Output is correct
2 Correct 9 ms 13036 KB Output is correct
3 Correct 10 ms 13164 KB Output is correct
4 Correct 9 ms 13036 KB Output is correct
5 Correct 9 ms 13036 KB Output is correct
6 Correct 9 ms 13036 KB Output is correct
7 Correct 9 ms 13036 KB Output is correct
8 Correct 35 ms 22380 KB Output is correct
9 Correct 53 ms 26596 KB Output is correct
10 Correct 50 ms 24292 KB Output is correct
11 Correct 56 ms 26596 KB Output is correct
12 Correct 52 ms 24428 KB Output is correct
13 Correct 49 ms 24420 KB Output is correct
14 Correct 50 ms 23524 KB Output is correct
15 Correct 74 ms 28648 KB Output is correct
16 Correct 68 ms 28640 KB Output is correct
17 Correct 46 ms 26216 KB Output is correct
18 Runtime error 26 ms 13164 KB Execution failed because the return code was nonzero
19 Halted 0 ms 0 KB -