Submission #549224

#	Time	Username	Problem	Language	Result	Execution time	Memory
549224		ala2	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	1480 ms	45384 KiB

street_lamps

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

map<int,int>m;
map<int,int>l;
map<int,int>on;
string s;
int n,T;

int bit(int i)
{
    return s[i]=='1';
}
char f(char x)
{
    if(x=='1')
    {
        return '0';
    }
    else return '1';
}
int ff(int i,int j)
{
    for(int k=i;k<j;k++)
    {
        if(s[k]=='0')
            return 0;
    }
    return 1;
}
int ans[120][200];
signed main()
{
    cin>>n>>T;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='1')
            on[i]=1;

    }
    if(T<=100&&n<=100)
            while(T--)
    {
    {for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(ff(i,j))
                    ans[i][j]++;
            }
        }
        string c;
        cin>>c;
        if(c[0]=='q')
        {
            int a,b;
            cin>>a>>b;
            a--;
            b--;
            cout<<ans[a][b]<<endl;
        }
        else
        {
            int i;
            cin>>i;
            i--;
            if(s[i]=='1')
            s[i]='0';
            else s[i]='1';
        }

    }
    }
    for(int q=1;q<=T;q++)
    {
        string c;
        cin>>c;
        //cout<<"DS";
        if(c[0]=='q')
        {
            int a,b;
            cin>>a>>b;
            a--;
            m[a]+=(q-l[a])*on[a];         //   cout<<"         "<<q<<"     "<<l[a]<<"  "<<on[a]<<"  "<<m[a]<<endl;
       cout<<m[a]<<endl;
            l[a]=q;

        }
        else
        {
            int i;
            cin>>i;
            i--;
            if(on[i])
            {
                m[i]+=(q-l[i]);
            }
            on[i]=1-on[i];
            l[i]=q;
        }

    }

}

// 1
/*
6 10
101101
q 3 4       1
t 2         111101
q 3 4       3
q 2 3       3
t 1         011101
q 1 2       4
t 5         011111
t 6         011110
q 5 6       3
q 6 7       7

6 10
101101
q 3 4
t 2
q 3 4
q 2 3
t 1
q 1 2
t 5
t 6
q 5 6
q 6 7
*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20