#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 ];
void brute(const vector<ask> &qries) {
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] : qries) {
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;
}
}
}
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 solve()':
selling_rna.cpp:19:17: warning: statement has no effect [-Wunused-value]
19 | #define DE(...) 0
| ^
selling_rna.cpp:92:3: note: in expansion of macro 'DE'
92 | DE(al, ar, cl, cr);
| ^~
| # |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
19564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
- |
| # |
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 |
Incorrect |
227 ms |
19564 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
