What is standard method for this problem?
Using stac I prepeared next[100000] for each opening
and closing brackets.
But it is appeared as bad because 50000*100000 too big.
I made big jumps as next100[100000] and got Ac 0.203
Is my method can be beaten by new tests?

These tests have helped me to solve the problem.

Test #1
input:
A
1
1 1
output:
0

Test #2
input:
Aa
3
1 1
1 2
2 2
output:
010

Test #3
input:
AacCAa
5
1 6
1 2
1 4
2 3
5 6
output:
01001

Test #4
input:
AaCAac
6
1 6
1 2
3 6
4 5
2 3
1 5
output:
111100

check that (r - l) % 2 == 1

Who can give me a test...

I found my mistake. I have AC.

Edited by author 12.12.2010 15:33

11 authors lost AC. Thanks to Fedor Fominykh for new tests.

Which method can be used in this problem? Really dynamic programming? Give me this test if you can please... :)

My AC program gives answer "1" to the test:

GTACcAaa
1
1 8

Cannot beat test 41.
Please share any ideas, tricky tests.

#include <limits>
#include <fstream>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
#include <time.h>
#include <cmath>

#define fori(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forbi(i,a,b) for(int i = a; i<=b; i++)
#define len(v) (int((v).size()))
#define vi vector<int>
#define vvi vector<vi >
#define sz(v) (int)v.size()
#define mmin(a,b,c) min(a,min(b,c))
#define sqr(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define inf 987654321
#define mmax(a,b,c) max(a,max(b,c))
#define ii pair<int,int>
#define si pair<int,string>
#define sii vector<si >
#define vii vector<ii >
#define vs vector<string >
#define vvii vector<vii >
const double pi = acos(0.0)*2;
const double eps = 1e-7;
#define mp(a,b) make_pair(a,b)

using namespace std;

#ifndef ONLINE_JUDGE
ifstream cin("input.txt");
ofstream cout("output.txt");
#else
#include <iostream>
#endif

vii X;
vii Z;
vi V;
vi U;
vector < char > S;

void main()
{
    V.reserve(200001);
    char T [200001];
    X.reserve(200001);
    Z.reserve(200001);
    U.reserve(200001);

    int n;
    scanf("%s", T);
    scanf("%d",&n);
    int t=strlen(T);
    X=vii(n);
    V.resize(t);
    Z=vii(t);


    fori(i,n)
        scanf("%d%d",&(X[i].first),&(X[i].second));
    int y=0, max=0, Root=0, c=1;
    U.resize(t);
    S.reserve(200001);
    fori(i,t)
    {
        if (S.empty() && (T[i]=='a' || T[i]=='c' || T[i]=='g' || T[i]=='t'))
        {
            V[i]=1;
            Z[i].second=Root;
            if (i!=0)
                Z[i].first=Z[i-1].second;
            continue;
        }
        if (T[i]=='A' || T[i]=='C' || T[i]=='G' || T[i]=='T')
        {
            S.push_back(T[i]);
            if (i!=0)
                Z[i].first=Z[i-1].second;
            y++;
            if (y>max)
                max=y;
            Z[i].second=y+c;
        }
        else
        {
            if (S.back() - T[i] == 'A' - 'a')
            {
                S.pop_back();
                y--;
                Z[i].second=y+c;
                Z[i].first=Z[i-1].second;
                if (S.empty())
                {
                    Z[i].second=Root;
                    y=Root;
                    c++;
                }

            }
            else
            {
                V[i]=1;
                Z[i].first=Z[i-1].second;
                S.clear();
                Root=max+1;
                Z[i].second=Root;
                c++;
                y=Root;
            }
        }
    }
    /* fori(i,t)
        cout<<V[i].first<<" ";
    cout<<endl;
    fori(i,t)
        cout<<V[i].second<<" "; */

    //V.push_back(mp(0,0));
    U[0]=V[0];
    for(int i=1; i<t; i++)
        U[i]=U[i-1]+V[i];

    fori(j,n)
    {
        int d;
        if (X[j].first>1)
            d=U[X[j].second-1]-U[X[j].first-2];
        else
            d=U[X[j].second-1];

        if ((Z[X[j].first-1].first==Z[X[j].second-1].second) && d==0)
            printf("%d",1);
        else
            printf("%d",0);
    }
}

Edited by author 26.10.2009 23:17

Give me some test, please.

I was just wondering- are "ACac" and "ACCcca" human strands?