Submission #1158516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158516		12345678	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2089 ms	80480 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=0, ll r=0, ll t=0, ll type=0): 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], sz;
string opr, str;
set<pair<ll, ll>> rng;
vector<points> p, tmp;

struct segtree
{
    pair<ll, ll> d[12*nx];
    pair<ll, ll> sum(pair<ll, ll> l, pair<ll,ll> r)
    {
        return {l.first+r.first, l.second+r.second};
    }
    void update(int l, int r, int i, int idx, pair<ll, ll> vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=sum(d[i], vl), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=sum(d[2*i], d[2*i+1]);
    }
    pair<ll, ll> query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return {0, 0};
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return sum(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

void solve(int l, int r)
{
    if (l==r) return;
    int md=(l+r)/2;
    solve(l, md);
    solve(md+1, r);
    int idxl=l, idxr=md+1, idx=l;
    //cout<<"solve "<<l<<' '<<r<<'\n';
    while (idxl<=md||idxr<=r)
    {
        if (idxr>r||(idxl<=md&&p[idxl].r>=p[idxr].r))
        {
            if (p[idxl].type!=0) s.update(0, sz-1, 1, p[idxl].t, {p[idxl].t*p[idxl].type, p[idxl].type});
            tmp[idx]=p[idxl];
            idx++;
            idxl++;
        }
        else
        {
            if (p[idxr].type==0)
            {
                auto ans=s.query(0, sz-1, 1, 0, p[idxr].t);
                res[p[idxr].t]+=ans.first;
                cnt[p[idxr].t]+=ans.second;
            }
            tmp[idx]=p[idxr];
            idx++;
            idxr++;
        }
    }
    for (int i=l; i<=md; i++) if (p[i].type!=0) s.update(0, sz-1, 1, p[i].t, {-p[i].t*p[i].type, -p[i].type});
    for (int i=l; i<=r; i++) p[i]=tmp[i];
}

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';
    sort(p.begin(), p.end());
    //for (auto x:p) cout<<x.l<<' '<<x.r<<' '<<x.t<<' '<<x.type<<'\n';
    sz=p.size();
    tmp.resize(p.size());
    solve(0, sz-1);
    for (int i=1; i<=q ;i++)
    {
        if (qrs[i])
        {
            //cout<<"res "<<res[i]<<'\n';
            if (cnt[i]!=0) cout<<res[i]+qrs[i]<<'\n';
            else cout<<res[i]<<'\n';
        }
    }
}

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