MarioYC's blog

By MarioYC, 13 years ago, In English

Hi, I'm trying to solve this problem using binary search and range minimum query. However I'm getting RTE on test 15 (Finally found the error, AC now).


First, I consider '(' = +1 and ')' = -1 and calculate an array of accumulated sums, so when I want to find the longest regular sequence starting at some '(' at position s and the longest possible ending position will be e, we must have sum[i] >= sum[s] for every i such that s < i <= e+1, I find the maximum e where this is true using binary search and RMQ, since it is possible that sum[e+1] > sum[s]. I change e to the position where the minimum occurs and check that sum[e+1] = sum[s].

#include <cstdio>
#include <cstring>

using namespace std;

char s[1000001];
int sum[1000001],rmq[20][1000001],ind[20][1000001];

// want = 0 : value
// want = 1 : index
int solve(int s, int e, int want){
    int log = 0;
    
    while((1 << log) <= e-s+1) ++log;
    --log;
    
    if(rmq[log][s] < rmq[log][e - (1 << log) + 1]) return (want == 0? rmq[log][s] : ind[log][s]);
    return (want == 0? rmq[log][e - (1 << log) + 1] : ind[log][e - (1 << log) + 1]);
}

int main(){
    fgets(s,1000002,stdin);
    
    int L = strlen(s); --L;
    s[L] = 0;
    
    for(int i = 0;i < L;++i)
        sum[i + 1] = sum[i] + (s[i] == '('? 1 : -1);
    
    for(int i = 0;i <= L;++i){
        rmq[0][i] = sum[i];
        ind[0][i] = i;
    }
    
    for(int i = 1;i <= L;++i){
        rmq[0][i] = rmq[0][i - 1] + (s[i - 1] == '('? 1 : -1);
        ind[0][i] = i;
    }
    
    for(int l = 1,l2 = 2,j = 1;l2 <= L + 1;l <<= 1,l2 <<= 1,++j){
        for(int i = 0;i <= L;++i){
            if(i+l <= L){
                if(rmq[j-1][i] < rmq[j-1][i+l]){
                    rmq[j][i] = rmq[j-1][i];
                    ind[j][i] = ind[j-1][i];
                }else{
                    rmq[j][i] = rmq[j-1][i+l];
                    ind[j][i] = ind[j-1][i+l];
                }
            }else{
                rmq[j][i] = rmq[j-1][i];
                ind[j][i] = ind[j-1][i];
            }
        }
    }
    
    int ans = 0,cont = 1;
    
    for(int i = 0;i+1 < L;++i){
        if(s[i] == '('){
            int lo = i+1,hi = L,mi;
            
            while(lo != hi){
                mi = (lo + hi + 1) / 2;
                
                if(solve(i+1,mi,0) < rmq[0][i]) hi = mi - 1;
                else lo = mi;
            }
            
            lo = solve(i+1,lo,1);
            
            if(lo > i+1 && rmq[0][lo] == rmq[0][i]){
                int l = lo - i;
                
                if(ans == l) ++cont;
                else if(ans < l){
                    ans = l;
                    cont = 1;
                }
            }
        }
    }
    
    printf("%d %d\n",ans,cont);
    
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it