YEZAELP

o61_oct_c1_charprint

Dec 2nd, 2021
626
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. const int maxAZ = 26;
  6. const int maxN = 3e5;
  7. vector <int> AZ[maxAZ + 10];
  8. int szAZ[maxAZ + 10], curAZ[maxAZ + 10];
  9. int mark[maxN + 10];
  10.  
  11. int to_int(char a){
  12.     return a - 'a' + 1;
  13. }
  14.  
  15. int Sum(int pst, int n, int sum = 0){
  16.     for(int i=pst;i>=1;i-=i&-i)
  17.         sum += mark[i];
  18.     return sum;
  19. }
  20.  
  21. void Update(int pst, int n){
  22.     for(int i=pst;i<=n;i+=i&-i)
  23.         mark[i] ++;
  24. }
  25.  
  26. int main(){
  27.  
  28.     int k;
  29.     scanf("%d", &k);
  30.  
  31.     string prt;
  32.     cin >> prt;
  33.     int len_prt = prt.size();
  34.     for(int i=0;i<len_prt;i++){
  35.         char p = prt[i];
  36.         AZ[to_int(p)].push_back(i + 1);
  37.         szAZ[to_int(p)] ++;
  38.     }
  39.  
  40.     string str;
  41.     cin >> str;
  42.     int len_str = str.size();
  43.     long long ans = 0;
  44.     for(auto s: str){
  45.         int ints = to_int(s);
  46.         if(curAZ[to_int(s)] == szAZ[to_int(s)]){
  47.             printf("-1");
  48.             return 0;
  49.         }
  50.         int pst = AZ[ints][curAZ[ints]];
  51.         curAZ[ints] ++;
  52.         ans += pst;
  53.         if(k == 1){
  54.             ans -= (long long) Sum(pst, len_prt);
  55.             Update(pst, len_prt);
  56.         }
  57.     }
  58.  
  59.     printf("%lld", ans);
  60.  
  61.     return 0;
  62. }
RAW Paste Data