fork download
copy 
  1. //                                        nEro
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4.  
  5. using ll = long long;
  6.  
  7. const ll inf = 1e18;
  8. const int N = 2 * 1e5 + 10;
  9.  
  10. ll n, k;
  11. ll res;
  12. ll a[N];
  13. ll dp[N];
  14.  
  15. string s[N];
  16.  
  17. vector<string> v;
  18.  
  19. long long segtree[4 * N];
  20.  
  21. void build(int l , int r , int node){
  22.     if(l == r){
  23.         segtree[node] = s[l].size();
  24.     }
  25.     else{
  26.         int mid = l + r >> 1;
  27.         build(l , mid , node + node);
  28.         build(mid + 1 , r , node + node + 1);
  29.         ll can = min(segtree[node + node], segtree[node + node + 1]);
  30.         ll ans = 0;
  31.         for(int i = 0; i < can; ++i){
  32.             if(s[mid][i] != s[mid + 1][i])    break;
  33.             ++ans;
  34.         }
  35.         segtree[node] = ans;
  36.     }
  37. }
  38.  
  39. long long query(int l , int r , int node , int ql , int qr){
  40.     if(l > qr || r < ql){
  41.         return inf;
  42.     }
  43.     if(l >= ql && r <= qr){
  44.         return segtree[node];
  45.     }
  46.     int mid = l + r >> 1;
  47.     ll xx = query(l , mid , node + node , ql , qr);
  48.     ll yy = query(mid + 1 , r , node + node + 1 , ql , qr);
  49.     if(xx == inf)   return yy;
  50.     if(yy == inf)   return xx;
  51.     ll can = min(xx, yy);
  52.     ll ans = 0;
  53.     for(int i = 0; i < can; ++i){
  54.         if(s[mid][i] != s[mid + 1][i])    break;
  55.         ++ans;
  56.     }
  57.     return ans;
  58. }
  59.  
  60. bool ok(ll m, ll n){
  61.     for(int i = 1; i <= n; ++i){
  62.         if(i + k - 1 <= n){
  63.             if(query(1, n, 1, i, i + k - 1) >= m)   return true;
  64.         }
  65.     }
  66.     return false;
  67. }
  68.  
  69. void solve(){
  70.     ll ans = 0, gg = 0;
  71.     cin >> n >> k;
  72.     for(int i = 1; i <= n; ++i){
  73.         cin >> s[i];
  74.         gg = max(gg, (ll)s[i].size());
  75.     }
  76.     sort(s + 1, s + n + 1);
  77.     ll cur = n;
  78.     while(cur){
  79.         ll lo = -1, hi = gg + 1;
  80.         build(1, cur, 1);
  81.         while(lo + 1 < hi){
  82.             ll m = lo + hi >> 1LL;
  83.             if(ok(m, cur))   lo = m;
  84.             else    hi = m;
  85.         }
  86.         if(lo <= 0) break;   
  87.         for(int i = 1; i <= cur; ++i){
  88.             if(i + k - 1 <= cur){
  89.                 if(query(1, cur, 1, i, i + k - 1) == lo){
  90.                     ans += lo;
  91.                     i += (k - 1);
  92.                 }
  93.                 else    v.push_back(s[i]);
  94.             }
  95.             else    v.push_back(s[i]);
  96.         }
  97.         for(int i = 1; i <= v.size(); ++i){
  98.             s[i] = v[i - 1];
  99.         }
  100.         cur = v.size();
  101.         v.clear();
  102.         gg = lo - 1;
  103.     }
  104.  
  105.     cout << "Case #" << ++res << ": " << ans << "\n";
  106. }
  107.  
  108. int main(int argc, char const *argv[]){
  109.     ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  110.     ll t = 1;
  111.     cin >> t;
  112.     while(t--){
  113.         solve();
  114.         v.clear();
  115.     }
  116. }
  117. //                                        orEn
Success #stdin #stdout 0s 9728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1: 0
https://ideone.com/HzUpGU
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!