//
//Vi läser input på formen N, sen N rader med strängar (ordlistan), sen M, sen M rader med par med strängar P och Q. Ex:
//
//N
//s1
//s2
//s3
//...
//sN
//M
//P1 Q1
//P2 Q2
//P3 Q3
// ...
//PM QM
//
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<long long> vl;
typedef vector<vector<long long>> vvl;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<pair<int, int>>> vvpii;
typedef pair<long long, long long> pll;
typedef vector<pair<long long, long long>> vpll;
typedef vector<vector<pair<long long, long long>>> vvpll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, b) for(auto &a : b)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define deb(x) cout << endl << #x << ": " << x << endl
#define deb2(x, y) cout << endl << #x << ": " << x << ", " << #y << ": " << y << endl
#define deb3(x, y, z) cout << endl << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl
#define debP(p) cout << endl << #p << ": " << p.first << ", " << p.second << endl
#define debArr(x) cout << endl << #x << ": "; rep(abc, 0, x.size()) cout << x[abc] << " "
#define el cout << endl
#define sz(x) x.size()
//number &= ~(1UL << n); -Turn off bit
//number |= (1UL << n); -Turn on bit
//number ^= (1UL << n); -Toggle bit
//bool on = (number & (1UL << n) -whether the n-th (0-indexed) bit is on or off
//Fenwick-träd
struct FT {
vector<ll> s;
FT(int n) : s(n) {}
void update(int pos, ll dif) { // a[pos] += dif
for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
}
ll query(int pos) { // sum of values in [0, pos)
ll res = 0;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
// Returns n if no sum is >= sum, or -1 if empty sum is.
if (sum <= 0) return -1;
int pos = 0;
for (int pw = 1 << 25; pw; pw >>= 1) {
if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
pos += pw, sum -= s[pos-1];
}
return pos;
}
};
int numbering = 0;
struct Item { // Vi sorterar queries och indexen som vi ska querya över. Detta är ett sätt att räkna ut antal tal i ett intervall < K
bool isQuery, isAddition; //Om itemet är en query eller bara element, och om svaret på eventuell query ska + eller - på svaret
int E; //Om itemet är ett element, så är detta värdet på elementet
int L, R, K, I; //För query: L, R beskriver intervallet (inclusive),
// K beskriver vilket för vilket tal vi queriar under (prioriteten), I är index på svaret som vi ska uppdatera efter denna query
int number = numbering++;
Item(bool isQuery, int E) : isQuery(isQuery), E(E) {};
Item(bool isQuery, int L, int R, int K, int I, bool isAddition) : isQuery(isQuery), L(L), R(R), K(K), I(I), isAddition(isAddition) {};
};
bool comp(const Item& A, const Item& B) { //Jämför to-do-list items för sorteringen
int pA = A.isQuery ? A.K : A.E;
int pB = B.isQuery ? B.K : B.E;
if (pA == pB) {
if (A.isQuery && !B.isQuery) return true;
if (!A.isQuery && B.isQuery) return false;
return (A.number < B.number);
}
return pA < pB;
}
int N; //Antal ord
int M; //Antal queries
vs A; //Vektorn med alla ord sorterade i bokstavsordning
vs B; //Vektorn med alla ord baklänges sorterade i bokstavsordning
vector<Item> toDoList;
vi ftIndex;
vector<string> ps, qs;
unordered_set<ll> pref, suff;
const ll base = 128923;
unordered_map<string, pii> intervalsA;
unordered_map<string, pii> intervalsB;
void savePrefix(unordered_map<string, pii>& intervals, string& prefix, int index) {
if (intervals.find(prefix) == intervals.end()) {
intervals[prefix].first = index;
}
intervals[prefix].second = index;
}
void preCalculateIntervals() {
rep(i, 0, N) { //Loopa igenom varje ord
string current = "";
ll h = 0;
rep(j, 0, sz(A[i])) { //Loopa igenom alla möjliga prefix för ordet A[i]
h *= base;
h += A[i][j];
current += A[i].at(j);
if(pref.find(h) != pref.end())savePrefix(intervalsA, current, i); //Spara prefixet (om det är den första eller sista förekomsten)
}
current = "";
h = 0;
rep(j, 0, sz(B[i])) { //Gör samma med alla ord i B
h *= base;
h += B[i][j];
current += B[i].at(j);
if(suff.find(h) != suff.end())savePrefix(intervalsB, current, i);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
vector<pair<string, int>> B_andToA;
rep(i, 0, N) { //Läs in alla ord, och bygg upp ordlistorna
string ord; cin >> ord;
A.pb(ord);
}
sort(all(A)); //Sortera ordlistan A
rep(i, 0, N) {
string ord = A[i];
reverse(all(ord));
B_andToA.pb(mp(ord, i));
}
sort(all(B_andToA)); //Sortera ordlistan B
ftIndex.resize(N);
rep(i, 0, sz(B_andToA)) {
B.pb(B_andToA[i].first);
ftIndex[i] = B_andToA[i].second; //Spara vilket index varje tal i fenwickträdet kommer ha, så vi kan uppdatera det snabbt
}
rep(c1,0,M){
string P, Q; cin >> P >> Q;
ps.push_back(P);
qs.push_back(Q);
ll h = 0;
trav(ch, P){
h *= base;
h += ch;
}
pref.insert(h);
h = 0;
reverse(all(Q));
trav(ch, Q){
h *= base;
h += ch;
}
suff.insert(h);
}
preCalculateIntervals();
vi ans(M, 0);
rep(i, 0, M) { //Lägg in alla queries i "to-do-listan"
string P, Q; P = ps[i]; Q = qs[i];
reverse(all(Q));
if (intervalsA.find(P) == intervalsA.end() || intervalsB.find(Q) == intervalsB.end()) continue;
pii intervalA = intervalsA[P];
pii intervalB = intervalsB[Q];
int LA = intervalA.first;
int RA = intervalA.second;
int LB = intervalB.first;
int RB = intervalB.second;
Item itemR(true, LA, RA, RB + 1, i, true);
Item itemL(true, LA, RA, LB, i, false);
toDoList.pb(itemR);
toDoList.pb(itemL);
}
rep(i, 0, N) { //Lägg till alla index också, som vi ska querya efter i ordning
Item item(false, i);
toDoList.pb(item);
}
sort(all(toDoList), comp);
FT ft(N);
trav(item, toDoList) {
if (item.isQuery) { //Om det vi ska göra nu är att hantera en query
ll res = ft.query(item.R + 1) - ft.query(item.L);
ans[item.I] += (1 - (2 * !item.isAddition)) * res;
}else { //Om det vi ska göra nu är att lägga till ett till index
int pos = ftIndex[item.E];
ft.update(pos, 1);
}
}
trav(a, ans) {
cout << a << "\n";
}
}
Compilation message
selling_rna.cpp: In member function 'void FT::update(int, ll)':
selling_rna.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
| ^
selling_rna.cpp: In member function 'int FT::lower_bound(ll)':
selling_rna.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
| ^
selling_rna.cpp: In constructor 'Item::Item(bool, int, int, int, int, bool)':
selling_rna.cpp:84:18: warning: 'Item::I' will be initialized after [-Wreorder]
84 | int L, R, K, I; //För query: L, R beskriver intervallet (inclusive),
| ^
selling_rna.cpp:82:19: warning: 'bool Item::isAddition' [-Wreorder]
82 | bool isQuery, isAddition; //Om itemet är en query eller bara element, och om svaret på eventuell query ska + eller - på svaret
| ^~~~~~~~~~
selling_rna.cpp:88:5: warning: when initialized here [-Wreorder]
88 | Item(bool isQuery, int L, int R, int K, int I, bool isAddition) : isQuery(isQuery), L(L), R(R), K(K), I(I), isAddition(isAddition) {};
| ^~~~
selling_rna.cpp: In function 'void preCalculateIntervals()':
selling_rna.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
| ^
selling_rna.cpp:127:9: note: in expansion of macro 'rep'
127 | rep(j, 0, sz(A[i])) { //Loopa igenom alla möjliga prefix för ordet A[i]
| ^~~
selling_rna.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
| ^
selling_rna.cpp:135:9: note: in expansion of macro 'rep'
135 | rep(j, 0, sz(B[i])) { //Gör samma med alla ord i B
| ^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
| ^
selling_rna.cpp:165:5: note: in expansion of macro 'rep'
165 | rep(i, 0, sz(B_andToA)) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
729 ms |
12380 KB |
Output is correct |
| 2 |
Correct |
721 ms |
14736 KB |
Output is correct |
| 3 |
Correct |
734 ms |
14364 KB |
Output is correct |
| 4 |
Correct |
726 ms |
14820 KB |
Output is correct |
| 5 |
Correct |
146 ms |
12168 KB |
Output is correct |
| 6 |
Correct |
149 ms |
12140 KB |
Output is correct |
| 7 |
Correct |
1342 ms |
18132 KB |
Output is correct |
| 8 |
Correct |
222 ms |
21316 KB |
Output is correct |
| 9 |
Correct |
190 ms |
21984 KB |
Output is correct |
| 10 |
Correct |
338 ms |
13060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
18396 KB |
Output is correct |
| 2 |
Correct |
70 ms |
10100 KB |
Output is correct |
| 3 |
Correct |
87 ms |
12600 KB |
Output is correct |
| 4 |
Correct |
72 ms |
12512 KB |
Output is correct |
| 5 |
Correct |
70 ms |
10080 KB |
Output is correct |
| 6 |
Correct |
90 ms |
12600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
729 ms |
12380 KB |
Output is correct |
| 9 |
Correct |
721 ms |
14736 KB |
Output is correct |
| 10 |
Correct |
734 ms |
14364 KB |
Output is correct |
| 11 |
Correct |
726 ms |
14820 KB |
Output is correct |
| 12 |
Correct |
146 ms |
12168 KB |
Output is correct |
| 13 |
Correct |
149 ms |
12140 KB |
Output is correct |
| 14 |
Correct |
1342 ms |
18132 KB |
Output is correct |
| 15 |
Correct |
222 ms |
21316 KB |
Output is correct |
| 16 |
Correct |
190 ms |
21984 KB |
Output is correct |
| 17 |
Correct |
338 ms |
13060 KB |
Output is correct |
| 18 |
Correct |
102 ms |
18396 KB |
Output is correct |
| 19 |
Correct |
70 ms |
10100 KB |
Output is correct |
| 20 |
Correct |
87 ms |
12600 KB |
Output is correct |
| 21 |
Correct |
72 ms |
12512 KB |
Output is correct |
| 22 |
Correct |
70 ms |
10080 KB |
Output is correct |
| 23 |
Correct |
90 ms |
12600 KB |
Output is correct |
| 24 |
Correct |
437 ms |
18072 KB |
Output is correct |
| 25 |
Correct |
318 ms |
23184 KB |
Output is correct |
| 26 |
Correct |
575 ms |
16032 KB |
Output is correct |
| 27 |
Correct |
447 ms |
18228 KB |
Output is correct |
| 28 |
Correct |
530 ms |
49540 KB |
Output is correct |
| 29 |
Correct |
288 ms |
39908 KB |
Output is correct |
