Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<ll,ll> pii;
- # define im INT_MAX
- # define umap unordered_map
- # define uset unordered_set
- # define f first
- # define s second
- # define pq priority_queue
- # define pb push_back
- # define ins insert
- # define INF LLONG_MAX
- #define int long long
- int zero = 0;
- umap<int,int> targets; int pos[100005];
- int pref[100005]; int hits[100005];
- int pref_l1[100005]; int hits_l1[100005];
- int pref_r1[100005]; int hits_r1[100005];
- int pref_l2[100005]; int hits_l2[100005];
- int pref_r2[100005]; int hits_r2[100005];
- main(){
- // ifstream cin("test.in");
- // ofstream cout("test.out");
- int t, c; cin >> t >> c;
- for (int i=0; i<t; i++){int ti; cin >> ti; targets[ti] = LLONG_MAX;}
- string instructions; cin >> instructions;
- for (int i=1; i<=c; i++){
- if (instructions[i-1]=='L'){pos[i]=-1;}
- if (instructions[i-1]=='R'){pos[i]=1;}
- }
- for (int i=1; i<=c; i++){pref[i] = pref[i-1] + pos[i];}
- for (int i=1; i<=c; i++){pref_l1[i]=pref[i]-1;}
- for (int i=1; i<=c; i++){pref_l2[i]=pref[i]-2;}
- for (int i=1; i<=c; i++){pref_r1[i]=pref[i]+1;}
- for (int i=1; i<=c; i++){pref_r2[i]=pref[i]+2;}
- //targets[i]: which instruction hit the target at location i
- umap<int,int> targets_copy = targets;
- for (int i=1; i<=c; i++){
- hits[i] = hits[i-1];
- if (!pos[i] && targets_copy.count(pref[i])){hits[i]++; targets_copy.erase(pref[i]); targets[pref[i]] = i;}
- }
- targets_copy = targets;
- set<int> waiting; // waiting contains indices of all targets that are hit in original but weren't counted in hits earlier
- map<int, int> w2;
- for (int i=c; i>0; i--){
- hits_l1[i] = hits_l1[i+1];
- if (waiting.count(i)){hits_l1[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
- if (!pos[i] && targets_copy.count(pref_l1[i])){
- if (targets[pref_l1[i]] >= i){hits_l1[i]++; targets_copy.erase(pref_l1[i]);}
- else {waiting.insert(targets[pref_l1[i]]); w2[targets[pref_l1[i]]] = pref_l1[i];}
- }
- }
- targets_copy = targets; waiting.clear(); w2.clear();
- for (int i=c; i>0; i--){
- hits_l2[i] = hits_l2[i+1];
- if (waiting.count(i)){hits_l2[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
- if (!pos[i] && targets_copy.count(pref_l2[i])){
- if (targets[pref_l2[i]] >= i){hits_l2[i]++; targets_copy.erase(pref_l2[i]);}
- else {waiting.insert(targets[pref_l2[i]]);w2[targets[pref_l2[i]]] = pref_l2[i];}
- }
- }
- targets_copy = targets; waiting.clear();w2.clear();
- for (int i=c; i>0; i--){
- hits_r1[i] = hits_r1[i+1];
- if (waiting.count(i)){hits_r1[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
- if (!pos[i] && targets_copy.count(pref_r1[i])){
- if (targets[pref_r1[i]] >= i){hits_r1[i]++; targets_copy.erase(pref_r1[i]);}
- else {waiting.insert(targets[pref_r1[i]]);w2[targets[pref_r1[i]]] = pref_r1[i];}
- }
- }
- targets_copy = targets; waiting.clear();w2.clear();
- for (int i=c; i>0; i--){
- hits_r2[i] = hits_r2[i+1];
- if (waiting.count(i)){hits_r2[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
- if (!pos[i] && targets_copy.count(pref_r2[i])){
- if (targets[pref_r2[i]] >= i){hits_r2[i]++; targets_copy.erase(pref_r2[i]);}
- else {waiting.insert(targets[pref_r2[i]]);w2[targets[pref_r2[i]]] = pref_r2[i];}
- }
- }
- // cout << instructions << '\n';
- // printArray(pref_l2,c+1);
- // printArray(pref_l1,c+1);
- // printArray(pref,c+1);
- // printArray(pref_r1,c+1);
- // printArray(pref_r2,c+1);
- // cout << '\n';
- // printArray(hits_l2,c+1);
- // printArray(hits_l1,c+1);
- // printArray(hits,c+1);
- // printArray(hits_r1,c+1);
- // printArray(hits_r2,c+1);
- // need to know for each index that you change whether it is already fired at before and after
- // L to F means if it wasn't hit before or after it is now
- // L to R means nothing
- // F to L means if it wasn't hit before or after it won't be now
- int ans = hits[c];
- // try switching each value of pos to the other two
- for (int i=1; i<=c; i++){
- if (pos[i]==-1){ // L
- // int num_hits = hits[i-1] + hits_r1[i+1];
- // if (targets.count(pref_r1[i])){num_hits++;} targets.erase(pref_r1[i]);
- ans = max(ans,(hits[i-1] + hits_r1[i])); // L to F
- ans = max(ans,(hits[i-1] + hits_r2[i])); // L to R
- } else if (pos[i]==0){ // F
- ans = max(ans,(hits[i-1] + hits_l1[i])); // F to L
- ans = max(ans,(hits[i-1] + hits_r1[i])); // F to R
- // if (targets.count(pref[i])){targets.erase(pref[i]);}
- } else { // R
- // int num_hits = hits[i-1] + hits_l1[i+1];
- // if (targets.count(pref_l1[i])){num_hits++;} targets.erase(pref_l1[i]);
- ans = max(ans,hits[i-1] + hits_l1[i]); // R to F
- ans = max(ans,(hits[i-1] + hits_l2[i])); // R to L
- }
- // cout << ans << ' ' << i << '\n';
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment