206992026-01-08 18:00:03algoproDNScpp17Wrong answer 38/40212ms16628 KiB
// UUID: eea011d4-03f3-41e6-ba97-79a6b0c2f8fb
#include <bits/stdc++.h>
using namespace std;
string dns;
int n;
int solve(char c)
{
    int ans = 0;
    vector <int> v(n+1), p(n+1);
    unordered_map <int,int> m;
    vector <array <int,3>> t;
    for(int i = 1; i <= n; i++){
        if(dns[i] == c) v[i]++;
        else v[i]--;
    }
    for(int i = 1; i <= n; i++){
       p[i] = p[i-1] + v[i];
       if(m[p[i]] == 0) m[p[i]] = i;
    }

    for(auto [key, val] : m){
        t.push_back({key,val});
    }
    int T = t.size();
    sort(t.rbegin(),t.rend());
    vector <int> s(T,2e9);
    int mini = 2e9;
    for(int i = T-1; i > 0; i--){
        mini = min(mini, t[i][1]);
        s[i] = mini;
    }
    for(int i = 1; i <= n; i++){
        int pos = 2e9;
        int l = 0, r = T-1;
        while(l <= r){
            int m = (l+r)/2;
            if(t[m][0] <= p[i]){
                pos = min(pos, m);
                r = m - 1;
            }
            else l = m + 1;
        }
        if(pos == 2e9) continue;
        ans = max(ans, i-s[pos]);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> dns;
    n = dns.size();
    dns = ' ' + dns;
    int a = solve('A'), c = solve('C'), g = solve('G'), t = solve('T');
    cout << max(a,max(c,max(g,t)));

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base38/40
1Accepted0/01ms508 KiB
2Accepted0/0212ms10576 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms508 KiB
5Accepted2/21ms316 KiB
6Wrong answer0/21ms452 KiB
7Accepted2/22ms316 KiB
8Accepted4/448ms3388 KiB
9Accepted4/479ms4660 KiB
10Accepted4/4103ms5304 KiB
11Accepted4/4128ms7116 KiB
12Accepted4/4135ms12452 KiB
13Accepted5/5170ms15920 KiB
14Accepted5/5201ms16628 KiB