Submission #742670

#	Time	Username	Problem	Language	Result	Execution time	Memory
742670		speedyArda	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	277 ms	28612 KiB

street_lamps

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 3e5+5;
vector<int> seg(MAXN * 2, 1e9);
int n, q;
void upd(int v, int val)
{
    for(seg[v += n] = val; v > 1; v >>= 1)
    {
        seg[v >> 1] = max(seg[v],seg[v ^ 1]);
    }
}

int get(int l, int r)
{
    int val = 0;
    for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
    {
        if(l & 1)
            val = max(val, seg[l++]);
        if(r & 1)   
            val = max(val, seg[--r]);
    }
    return val;
}
vector< pair<string, pair<int, int> > > queries(MAXN); 
string stats[MAXN];
int main() 
{
    cin >> n >> q;
    string in;
    cin >> in;
    in = " " + in;
    stats[0] = in;
    int maxdiff = 0;
    int ltog = 0, fque = 1e9;
    for(int i = 1; i <= q; i++)
    {
        cin >> queries[i].first;
        if(queries[i].first == "toggle")
        {
            cin >> queries[i].second.first;
            ltog = i;
        } else {
            cin  >> queries[i].second.first >> queries[i].second.second; 
            maxdiff = max(maxdiff, queries[i].second.second - queries[i].second.first);
            fque = min(fque, i);
        }
    }
    if(max(n, q) <= 100) // Subtask 1
    {
        for(int i = 1; i <= q; i++)
        {
            if(queries[i].first == "toggle")
            {
                in[queries[i].second.first] = (in[queries[i].second.first] == '1' ? '0' : '1');
                stats[i] = in;
            } else 
            {
                stats[i] = in;
                int pos = 0;
                for(int ava = 0; ava < i; ava++) {
                    string temp = stats[ava];
                    int beg = queries[i].second.first;
                    int end = queries[i].second.second;
                    while(beg < end)
                    {

                        if(temp[beg] == '1')
                            beg++;
                        else
                            break;
                    }
                    if(beg == end)
                        pos++;
                }

               cout << pos << "\n";

            }

        }
    } else 
    {
        if(maxdiff == 1) // Subtask 2
        {
            vector<int> roads(n+5, 0);
            vector<int> last(n+5, 0);
            
            for(int i = 1; i <= q; i++)
            {
                int idx = queries[i].second.first;
                if(queries[i].first == "toggle")
                {
                    if(in[idx] == '1')
                    {
                        roads[idx] += i - last[idx];
                        in[idx] = '0';
                    } else 
                    {
                        last[idx] = i;
                        in[idx] = '1';
                    }
                } else 
                {
                    int val = roads[idx];
                    if(in[idx] == '1')
                    {
                        val += i - last[idx];
                    }
                    cout << val << "\n";
                }
            }
        } else if(ltog < fque) // Subtask 4
        { 
            
        } else //Subtask 3  
        {
            for(int i = 1; i <= q; i++)
            {
                if(queries[i].first == "toggle")
                {
                    upd(queries[i].second.first, i);
                } else 
                {
                    int fi = get(queries[i].second.first, queries[i].second.second);
                    if(fi == 1e9)
                        cout << "0\n";
                    else
                        cout << i - fi + 1 << "\n";
                }
            }
        }
    }
}

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