23582023-01-11 12:36:10sztomiDNScpp11Hibás válasz 2/40400ms15368 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1 << 18;
vector<int> fa;


int bal_ind(int x){
    return x*2;
}

int jobb_ind(int x){
    return x*2+1;
}

int hozzaad(int akt, int bal, int jobb, int cel, int ertek){
    if(jobb < cel || cel < bal) return -1;
    if(jobb == bal){
        fa[akt] = max(fa[akt], ertek);
        return fa[akt];
    }

    int kozep = (bal + jobb) / 2;
    if(cel <= kozep){
        fa[akt] = max(fa[akt], hozzaad(bal_ind(akt), bal, kozep, cel, ertek));
    }
    else{
        fa[akt] = max(fa[akt], hozzaad(jobb_ind(akt), kozep+1, jobb, cel, ertek));
    }
    return fa[akt];
}

int lekerdez(int akt, int bal, int jobb, int k_bal, int k_jobb){
    if(k_bal > k_jobb) return -1;
    if(jobb < k_bal || k_jobb < bal) return -1;
    if(bal == jobb){
        return fa[akt];
    }
    if(k_bal == bal && k_jobb == jobb){
        return fa[akt];
    }
    int kozep = (bal + jobb) / 2;
    int ki = lekerdez(bal_ind(akt), bal, kozep, k_bal, min(kozep, k_jobb));
    ki = max(ki, lekerdez(jobb_ind(akt), kozep+1, jobb, max(k_bal, kozep+1), k_jobb));
    return ki;
}




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin>> s;
    int n = s.size();
    cout << n << "\n";
    string betuk = "ACGT";
    map<char, vector<int>> db;
    vector<int> ideigl(n+1, 0);
    int prev;
    for(char c : betuk){
        prev = 0;
        for(int i = 0; i < n; i++){
            if(s[i] == c){
                ideigl[i+1] = ++prev;
            }
            else{
                ideigl[i+1] = --prev;
            }
        }
        db.insert({c, ideigl});
    }

    int ki = 1;
    int temp;
    for(char c : betuk){
        //if(c != 'T') continue;
/*
        cout << c << ": ";
        for(int x : db[c]){
            cout << x << " ";
        }
        cout << "\n";
*/
        fa.assign(2*MAXN, -1);
        vector<int> v = db[c];
        for(int i = n; i > 0; i--){
            hozzaad(1, 0, MAXN-1, n+v[i], i);
            temp = lekerdez(1, 0, MAXN-1, n+v[i-1], 400000);
            //cout << i << " " << temp << " " << temp-i+1 << "\n";
            ki = max(ki, temp - i + 1);
        }
    }

    cout << ki << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/40
1Hibás válasz0/04ms5756 KiB
2Időlimit túllépés0/0400ms8480 KiB
3Hibás válasz0/24ms6252 KiB
4Hibás válasz0/24ms6452 KiB
5Hibás válasz0/24ms6572 KiB
6Elfogadva2/26ms6780 KiB
7Hibás válasz0/26ms7100 KiB
8Hibás válasz0/4114ms9648 KiB
9Hibás válasz0/4180ms11476 KiB
10Hibás válasz0/4222ms12624 KiB
11Hibás válasz0/4291ms14388 KiB
12Időlimit túllépés0/4317ms15368 KiB
13Időlimit túllépés0/5312ms9772 KiB
14Időlimit túllépés0/5375ms10384 KiB