Submission #1158304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158304		12345678	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5094 ms	50876 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;

#define ll long long

struct points
{
    ll l, r, t, type, idx;
    points(ll l, ll r, ll t, ll type): l(l), r(r), t(t), type(type){}
    bool operator<(const points &o) const
    {
        if (l!=o.l) return l>o.l;
        if (r!=o.r) return r<o.r;
        return t<o.t;
    }
};

ll n, q, open[nx], qrs[nx], a, b, l, r, lst, on, res[nx], cnt[nx];
string opr, str;
set<pair<ll, ll>> rng;
vector<points> p;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q>>str;
    str=' '+str+'0';
    for (int i=1; i<=n+1; i++)
    {
        if (str[i]=='0')
        {
            if (on)
            {
                rng.insert({lst, i-1});
                p.push_back(points(lst, i-1, 0, -1));
                on=0;
            }
        }
        else if (!on) on=1, lst=i;
    }
    for (int i=1; i<=n; i++) open[i]=str[i]=='1';
    for (int i=1; i<=q; i++)
    {
        cin>>opr;
        if (opr[0]=='t')
        {
            cin>>a;
            if (open[a])
            {
                auto vl=*prev(rng.upper_bound(make_pair(a, INT_MAX)));
                rng.erase(vl);
                p.push_back(points(vl.first, vl.second, i, 1));
                if (a!=vl.first) p.push_back(points(vl.first, a-1, i, -1)), rng.insert({vl.first, a-1});
                if (a!=vl.second) p.push_back(points(a+1, vl.second, i, -1)), rng.insert({a+1, vl.second});
            }
            else
            {
                l=r=a;
                auto itrr=rng.upper_bound(make_pair(a, INT_MAX));
                if (itrr!=rng.end()&&itrr->first==a+1)
                {
                    r=itrr->second;
                    p.push_back(points(itrr->first, itrr->second, i, 1));
                    rng.erase(itrr);
                }
                auto itrl=rng.upper_bound(make_pair(a, INT_MAX));
                if (itrl!=rng.begin()&&(--itrl)->second==a-1)
                {
                    l=itrl->first;
                    p.push_back(points(itrl->first, itrl->second, i, 1));
                    rng.erase(itrl);
                }
                rng.insert({l, r});
                p.push_back(points(l, r, i, -1));
            }
            open[a]=!open[a];
        }
        else
        {
            qrs[i]=i;
            cin>>a>>b;
            p.push_back(points(a, b-1, i, 0));
        }
    }
    //for (auto x:p) cout<<x.l<<' '<<x.r<<' '<<x.t<<' '<<x.type<<'\n';
    for (auto x:p)
    {
        if (x.type==0)
        {
            for (auto y:p)
            {
                if (y.type!=0&&y.l<=x.l&&x.r<=y.r&&y.t<=x.t)
                {
                    //if (x.t==7) cout<<"here "<<y.t<<'\n';
                    res[x.t]+=y.t*y.type;
                    cnt[x.t]++;
                }
            }
        }
    }
    for (int i=1; i<=q ;i++)
    {
        if (qrs[i])
        {
            //cout<<"before "<<res[i]<<'\n';
            if (cnt[i]%2) cout<<res[i]+qrs[i]<<'\n';
            else cout<<res[i]<<'\n';
        }
    }
}

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