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

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?

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

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

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?