2364 2023. 01. 11 12:47:41 sztomi DNS cpp11 Elfogadva 40/40 293ms 14476 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];
    }
    if(fa[akt] == -1){
        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();
    string betuk = "ACGT";
    vector<vector<int>> db(4, vector<int>(n+1, 0));
    char c;
    for(int i = 0; i < 4; i++){
        c = betuk[i];
        for(int j = 0; j < n; j++){
            if(s[j] == c){
                db[i][j+1] = db[i][j]+1;
            }
            else{
                db[i][j+1] = db[i][j]-1;
            }
        }
    }

    int ki = 1;
    int temp;
    set<int> valt;
    fa.assign(2*MAXN, -1);
    for(int j = 0; j < 4; j++){
        for(int i = n; i > 0; i--){
            hozzaad(1, 0, MAXN-1, n+db[j][i], i);
            temp = lekerdez(1, 0, MAXN-1, n+db[j][i-1], 400000);
            ki = max(ki, temp - i + 1);
        }
        for(int& x : fa){
            x = -1;
        }
    }

    cout << ki << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 4ms 5572 KiB
2 Elfogadva 0/0 293ms 12772 KiB
3 Elfogadva 2/2 4ms 6008 KiB
4 Elfogadva 2/2 4ms 6164 KiB
5 Elfogadva 2/2 4ms 6368 KiB
6 Elfogadva 2/2 4ms 6440 KiB
7 Elfogadva 2/2 6ms 6696 KiB
8 Elfogadva 4/4 78ms 8372 KiB
9 Elfogadva 4/4 122ms 9640 KiB
10 Elfogadva 4/4 150ms 10616 KiB
11 Elfogadva 4/4 194ms 11688 KiB
12 Elfogadva 4/4 218ms 12664 KiB
13 Elfogadva 5/5 257ms 13756 KiB
14 Elfogadva 5/5 284ms 14476 KiB