fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define ld long double
  7. #define eb emplace_back
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define nn '\n'
  12. #define pi pair<int, int>
  13. #define unmp unordered_map
  14. #define uns unordered_set
  15. #define lb lower_bound
  16. #define ub upper_bound
  17. #define pq priority_queue
  18. #define TASK " "
  19.  
  20. const int INF = 1e18;
  21. const int mod = 1e9+7;
  22. const int N = 2e5 + 5;
  23. int MOD = 998244353;
  24. int bit[200000];
  25. int n, q, k, d;
  26. string s;
  27. int a[N];
  28. int b[N];
  29. int c[N];
  30. int p[N];
  31. int pm[N];
  32. int lans, rans;
  33. int kq = -2;
  34. bool check(int m, int r){
  35.     return p[r] - pm[m - 1] > 0;
  36. }
  37. bool anhphucbell(int x){
  38.     for(int i = 1;i <= n; i++){
  39.         p[i] = p[ i - 1] + a[i];
  40.         pm[i] = min(pm[i - 1], p[i]);
  41.     }
  42.  
  43.     for(int  r = 1; r <= n; r++){
  44.         int l_ = 1, r_ = r, ans = -1;
  45.         while(l_ <= r_){
  46.             int mid = (l_ + r_) / 2;
  47.             if(check(mid, r)){
  48.                 ans = mid;
  49.                 r_ = mid - 1;
  50.             }
  51.             else l_ = mid + 1;
  52.         }
  53.         if(ans != -1){
  54.             if(r - ans + 1 >= d){
  55.                 lans = ans;
  56.                 rans = r;
  57.                 return true;
  58.             }
  59.         }
  60.     }
  61.     return false;
  62. }
  63. signed main(){
  64.     ios_base::sync_with_stdio(0);
  65.     cin.tie(0);
  66.     cout.tie(0);
  67.     cin >> n;
  68.     cin >> s;
  69.     for(int i  = 1; i <= n; i++){
  70.         if(s[i - 1] == 'a'){
  71.         	a[i]++;
  72.         	b[i]--;
  73.         	c[i]--;
  74.         }
  75.         else if(s[i - 1] == 'b'){
  76.         	a[i]--;
  77.         	b[i]++;
  78.         	c[i]--;
  79.         }
  80.         else if(s[i - 1] == 'c'){
  81.         	a[i]--;
  82.         	b[i]--;
  83.         	c[i]++;
  84.         }
  85.     }
  86.     memset(p, 0, sizeof(p));
  87.     memset(pm, 0, sizeof(pm));
  88.     for(int i = 1;i <= n; i++){
  89.         p[i] = p[ i - 1] + a[i];
  90.         pm[i] = min(pm[i - 1], p[i]);
  91.     }
  92.     for(int  r = 1; r <= n; r++){
  93.         int l_ = 1, r_ = r, ans = -1;
  94.         while(l_ <= r_){
  95.             int mid = (l_ + r_) / 2;
  96.             if(check(mid, r)){
  97.                 ans = mid;
  98.                 r_ = mid - 1;
  99.             }
  100.             else l_ = mid + 1;
  101.         }
  102.         if(ans != -1){
  103.             kq = max(kq, r - ans + 1);
  104.         	}
  105.     }
  106.  
  107.  
  108.     memset(p, 0, sizeof(p));
  109.     memset(pm, 0, sizeof(pm));
  110.     for(int i = 1;i <= n; i++){
  111.         p[i] = p[ i - 1] + b[i];
  112.         pm[i] = min(pm[i - 1], p[i]);
  113.     }
  114.     for(int  r = 1; r <= n; r++){
  115.         int l_ = 1, r_ = r, ans = -1;
  116.         while(l_ <= r_){
  117.             int mid = (l_ + r_) / 2;
  118.             if(check(mid, r)){
  119.                 ans = mid;
  120.                 r_ = mid - 1;
  121.             }
  122.             else l_ = mid + 1;
  123.         }
  124.         if(ans != -1){
  125.             kq = max(kq, r - ans + 1);
  126.         }
  127.     }
  128.     memset(p, 0, sizeof(p));
  129.     memset(pm, 0, sizeof(pm));
  130.     for(int i = 1;i <= n; i++){
  131.         p[i] = p[ i - 1] + c[i];
  132.         pm[i] = min(pm[i - 1], p[i]);
  133.     }
  134.     for(int  r = 1; r <= n; r++){
  135.         int l_ = 1, r_ = r, ans = -1;
  136.         while(l_ <= r_){
  137.             int mid = (l_ + r_) / 2;
  138.             if(check(mid, r)){
  139.                 ans = mid;
  140.                 r_ = mid - 1;
  141.             }
  142.             else l_ = mid + 1;
  143.         }
  144.         if(ans != -1){
  145.             kq = max(kq, r - ans + 1);
  146.         }
  147.     }
  148.  
  149.     cout << kq << nn;
  150.     return 0;
  151. }
  152.  
Success #stdin #stdout 0.01s 7168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-2
https://ideone.com/ruZdQr
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

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!