a_chn

Untitled

Oct 28th, 2024
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,ll> pii;
  5. # define im INT_MAX
  6. # define umap unordered_map
  7. # define uset unordered_set
  8. # define f first
  9. # define s second
  10. # define pq priority_queue
  11. # define pb push_back
  12. # define ins insert
  13. # define INF LLONG_MAX
  14.  
  15. #define int long long
  16. int zero = 0;
  17. umap<int,int> targets; int pos[100005];
  18. int pref[100005]; int hits[100005];
  19. int pref_l1[100005]; int hits_l1[100005];
  20. int pref_r1[100005]; int hits_r1[100005];
  21. int pref_l2[100005]; int hits_l2[100005];
  22. int pref_r2[100005]; int hits_r2[100005];
  23.  
  24. main(){
  25.     // ifstream cin("test.in");
  26.     // ofstream cout("test.out");
  27.  
  28.     int t, c; cin >> t >> c;
  29.     for (int i=0; i<t; i++){int ti; cin >> ti; targets[ti] = LLONG_MAX;}
  30.     string instructions; cin >> instructions;
  31.     for (int i=1; i<=c; i++){
  32.         if (instructions[i-1]=='L'){pos[i]=-1;}
  33.         if (instructions[i-1]=='R'){pos[i]=1;}
  34.     }
  35.  
  36.  
  37.     for (int i=1; i<=c; i++){pref[i] = pref[i-1] + pos[i];}
  38.     for (int i=1; i<=c; i++){pref_l1[i]=pref[i]-1;}
  39.     for (int i=1; i<=c; i++){pref_l2[i]=pref[i]-2;}
  40.     for (int i=1; i<=c; i++){pref_r1[i]=pref[i]+1;}
  41.     for (int i=1; i<=c; i++){pref_r2[i]=pref[i]+2;}
  42.  
  43.     //targets[i]: which instruction hit the target at location i
  44.     umap<int,int> targets_copy = targets;
  45.     for (int i=1; i<=c; i++){
  46.         hits[i] = hits[i-1];
  47.         if (!pos[i] && targets_copy.count(pref[i])){hits[i]++; targets_copy.erase(pref[i]); targets[pref[i]] = i;}
  48.     }
  49.  
  50.     targets_copy = targets;
  51.     set<int> waiting; // waiting contains indices of all targets that are hit in original but weren't counted in hits earlier
  52.     map<int, int> w2;
  53.     for (int i=c; i>0; i--){
  54.         hits_l1[i] = hits_l1[i+1];
  55.         if (waiting.count(i)){hits_l1[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
  56.         if (!pos[i] && targets_copy.count(pref_l1[i])){
  57.             if (targets[pref_l1[i]] >= i){hits_l1[i]++; targets_copy.erase(pref_l1[i]);}
  58.             else {waiting.insert(targets[pref_l1[i]]); w2[targets[pref_l1[i]]] = pref_l1[i];}
  59.         }
  60.     }
  61.  
  62.     targets_copy = targets; waiting.clear(); w2.clear();
  63.     for (int i=c; i>0; i--){
  64.         hits_l2[i] = hits_l2[i+1];
  65.         if (waiting.count(i)){hits_l2[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
  66.         if (!pos[i] && targets_copy.count(pref_l2[i])){
  67.             if (targets[pref_l2[i]] >= i){hits_l2[i]++; targets_copy.erase(pref_l2[i]);}
  68.             else {waiting.insert(targets[pref_l2[i]]);w2[targets[pref_l2[i]]] = pref_l2[i];}
  69.         }
  70.     }
  71.  
  72.     targets_copy = targets; waiting.clear();w2.clear();
  73.     for (int i=c; i>0; i--){
  74.         hits_r1[i] = hits_r1[i+1];
  75.         if (waiting.count(i)){hits_r1[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
  76.         if (!pos[i] && targets_copy.count(pref_r1[i])){
  77.             if (targets[pref_r1[i]] >= i){hits_r1[i]++; targets_copy.erase(pref_r1[i]);}
  78.             else {waiting.insert(targets[pref_r1[i]]);w2[targets[pref_r1[i]]] = pref_r1[i];}
  79.         }
  80.     }
  81.  
  82.     targets_copy = targets; waiting.clear();w2.clear();
  83.     for (int i=c; i>0; i--){
  84.         hits_r2[i] = hits_r2[i+1];
  85.         if (waiting.count(i)){hits_r2[i]++; waiting.erase(i);targets_copy.erase(w2[i]);}
  86.         if (!pos[i] && targets_copy.count(pref_r2[i])){
  87.             if (targets[pref_r2[i]] >= i){hits_r2[i]++; targets_copy.erase(pref_r2[i]);}
  88.             else {waiting.insert(targets[pref_r2[i]]);w2[targets[pref_r2[i]]] = pref_r2[i];}
  89.         }
  90.     }
  91.  
  92.     // cout << instructions << '\n';
  93.  
  94.     // printArray(pref_l2,c+1);
  95.     // printArray(pref_l1,c+1);
  96.     // printArray(pref,c+1);
  97.     // printArray(pref_r1,c+1);
  98.     // printArray(pref_r2,c+1);
  99.     // cout << '\n';
  100.     // printArray(hits_l2,c+1);
  101.     // printArray(hits_l1,c+1);
  102.     // printArray(hits,c+1);
  103.     // printArray(hits_r1,c+1);
  104.     // printArray(hits_r2,c+1);
  105.  
  106.     // need to know for each index that you change whether it is already fired at before and after
  107.     // L to F means if it wasn't hit before or after it is now
  108.     // L to R means nothing
  109.     // F to L means if it wasn't hit before or after it won't be now
  110.  
  111.  
  112.     int ans = hits[c];
  113.     // try switching each value of pos to the other two
  114.     for (int i=1; i<=c; i++){
  115.         if (pos[i]==-1){ // L
  116.             // int num_hits = hits[i-1] + hits_r1[i+1];
  117.             // if (targets.count(pref_r1[i])){num_hits++;} targets.erase(pref_r1[i]);
  118.             ans = max(ans,(hits[i-1] + hits_r1[i])); // L to F
  119.             ans = max(ans,(hits[i-1] + hits_r2[i])); // L to R
  120.         } else if (pos[i]==0){ // F
  121.             ans = max(ans,(hits[i-1] + hits_l1[i])); // F to L
  122.             ans = max(ans,(hits[i-1] + hits_r1[i])); // F to R
  123.             // if (targets.count(pref[i])){targets.erase(pref[i]);}
  124.         } else { // R
  125.             // int num_hits = hits[i-1] + hits_l1[i+1];
  126.             // if (targets.count(pref_l1[i])){num_hits++;} targets.erase(pref_l1[i]);
  127.             ans = max(ans,hits[i-1] + hits_l1[i]); // R to F
  128.             ans = max(ans,(hits[i-1] + hits_l2[i])); // R to L
  129.         }
  130.         // cout << ans << ' ' << i << '\n';
  131.     }
  132.  
  133.     cout << ans << '\n';
  134.  
  135.  
  136.     return 0;
  137. }
Advertisement
Add Comment
Please, Sign In to add comment