Submission #332638

#	Time	Username	Problem	Language	Result	Execution time	Memory
332638		Kevin_Zhang_TW	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	74 ms	28648 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40