Submission #549141

#	Time	Username	Problem	Language	Result	Execution time	Memory
549141		ala2	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	339 ms	22936 KiB

street_lamps

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
//int a[1001000];
string s;
int n,T;
vector<pair<int,int>>anss;
vector<int>v[100100];
vector<int>von[100100];
vector<int>vtype[101000];
map<int,int>l;
int bit(int i)
{
    return s[i]=='1';
}
char f(char x)
{
    if(x=='1')
    {
        return '0';
    }
    else return '1';
}
signed main()
{
    cin>>n>>T;
    cin>>s;
    // A 1 B 2
    for(int i=0;i<n;i++)
    {
        v[i].pb(0);
        vtype[i].pb(1);
        if(s[i]=='1')
        {
            von[i].pb(1);
            l[i]=1;
        }
        else von[i].pb(0);
    }
    for(int q=1;q<=T;q++)
    {
        string c;
        cin>>c;
        if(c[0]=='q')
            c='B';
        else c='A';
        if(c=="A")
        {
            int i;
            cin>>i;
            i--;
            s[i]=f(s[i]);
            int nw=bit(i);
            v[i].pb(q);
            vtype[i].pb(1);
            von[i].pb(nw);
            continue;

        }
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        int i=a;
        v[i].pb(q);

        int x=von[i].size();
        while(!x)
        {

        }
        von[i].pb(von[i][x-1]);
        vtype[i].pb(2);
    }
    for(int i=0;i<n;i++)
    {
        von[i][0]=0;
    }
    /*
    cout<<endl;

    for(int i=0;i<=n;i++){
    for(auto j:v[i])
    cout<<j<<" ";
    cout<<endl;
    for(auto j:von[i])
    cout<<j<<" ";
    cout<<endl;
    for(auto j:vtype[i])
    cout<<j<<" ";
    cout<<endl;
    cout<<endl;
    }

*/
    for(int i=0;i<=n;i++)
    {
        int g=0;
        for(int j=1;j<v[i].size();j++)
        {       // cout<<"        "<<i<<endl;


            if(von[i][j-1]==1)
             g+=v[i][j]-v[i][j-1];
             if(j==1&&l[i])
                g+=v[i][j]-1;
            if(vtype[i][j]==2)
            {
                int x=g;
                x+=von[i][j];

                anss.pb({v[i][j],x});
            }
        }
    }
    sort(anss.begin(),anss.end());
    for(auto i:anss)
    {
        cout<<i.second<<endl;
    }
    return 0;

}

// 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
*/

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:100:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int j=1;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
street_lamps.cpp:104:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  104 |             if(von[i][j-1]==1)
      |             ^~
street_lamps.cpp:106:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  106 |              if(j==1&&l[i])
      |              ^~

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