Submission #1203925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203925		Hanksburger	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	5097 ms	110980 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, pair<int, int> > > upd[300005], qry[300005];
vector<pair<pair<int, int>, pair<int, int> > > vec;
int ans[300005], n, q, cnt, ind=1, one=1;
set<pair<int, int> > s;
string str;
struct node
{
    node *lc, *rc;
    int l, r, seg, lazy;
    pair<int, int> val;
    node(int l, int r) : lc(0), rc(0), l(l), r(r), seg(0), lazy(0) {}
};
void push(node *i)
{
    if (!i->lazy)
        return;
    int mid=(i->l+i->r)/2;
    if (!i->lc)
        i->lc=new node(i->l, mid);
    if (!i->rc)
        i->rc=new node(mid+1, i->r);
    i->lc->seg+=(mid-i->l+1)*i->lazy;
    i->lc->lazy+=i->lazy;
    i->rc->seg+=(i->r-mid)*i->lazy;
    i->rc->lazy+=i->lazy;
    i->lazy=0;
}
void update(node *&i, int &ql, int &qr, int &x)
{
    if (ql<=i->l && i->r<=qr)
    {
        i->seg+=(i->r-i->l+1)*x;
        i->lazy+=x;
        return;
    }
    push(i);
    int mid=(i->l+i->r)/2;
    if (i->l<=qr && ql<=mid)
    {
        if (!i->lc)
            i->lc=new node(i->l, mid);
        update(i->lc, ql, qr, x);
    }
    if (mid<qr && ql<=i->r)
    {
        if (!i->rc)
            i->rc=new node(mid+1, i->r);
        update(i->rc, ql, qr, x);
    }
    i->seg=(i->lc?i->lc->seg:0)+(i->rc?i->rc->seg:0);
}
int query(node *&i, int &ql, int &qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->seg;
    push(i);
    int mid=(i->l+i->r)/2, ans=0;
    if (i->lc && i->l<=qr && ql<=mid)
        ans+=query(i->lc, ql, qr);
    if (i->rc && mid<qr && ql<=i->r)
        ans+=query(i->rc, ql, qr);
    return ans;
}
void destruct(node *&i)
{
    if (i->lc)
        destruct(i->lc);
    if (i->rc)
        destruct(i->rc);
    delete i;
}
bool cmp(pair<pair<int, int>, pair<int, int> > &x, pair<pair<int, int>, pair<int, int> > &y)
{
    if (x.second.second!=y.second.second)
        return x.second.second>y.second.second;
    return x.first.first>y.first.first;
}
void recur(int l, int r)
{
    if (l==r)
        return;
    int mid=(l+r)/2;
    {
        vector<pair<pair<int, int>, pair<int, int> > > v;
        for (int i=l; i<=mid; i++)
            if (vec[i].first.first)
                v.push_back(vec[i]);
        for (int i=mid+1; i<=r; i++)
            if (!vec[i].first.first)
                v.push_back(vec[i]);
        sort(v.begin(), v.end(), cmp);
        node *root=new node(1, q);
        for (auto x:v)
        {
            if (x.first.first)
                update(root, x.second.first, q, x.first.second);
            else
                ans[x.first.second]+=query(root, one, x.second.first);
        }
        destruct(root);
    }
    recur(l, mid);
    recur(mid+1, r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q >> str;
    for (int i=1; i<=n; i++)
    {
        if (str[i-1]=='0')
        {
            s.insert({ind, i});
            upd[ind].push_back({1, {1, i}});
            upd[i+1].push_back({-1, {1, i}});
            ind=i+1;
        }
    }
    s.insert({ind, n+1});
    upd[ind].push_back({1, {1, n+1}});
    for (int i=1; i<=q; i++)
    {
        string t;
        cin >> t;
        if (t=="toggle")
        {
            int x;
            cin >> x;
            if (i==q)
                break;
            if (str[x-1]=='0')
            {
                str[x-1]='1';
                auto it=s.lower_bound({x+1, 0});
                pair<int, int> tmp1=*prev(it), tmp2=*it;
                s.erase(prev(it));
                s.erase(it);
                s.insert({tmp1.first, tmp2.second});
                upd[tmp1.first].push_back({-1, {i+1, tmp1.second}});
                upd[tmp2.first].push_back({1, {i+1, tmp1.second}});
                upd[tmp1.first].push_back({1, {i+1, tmp2.second}});
                upd[tmp2.first].push_back({-1, {i+1, tmp2.second}});
            }
            else
            {
                str[x-1]='0';
                auto it=prev(s.lower_bound({x+1, 0}));
                pair<int, int> tmp1={it->first, x}, tmp2={x+1, it->second};
                s.erase(it);
                s.insert(tmp1);
                s.insert(tmp2);
                upd[tmp1.first].push_back({-1, {i+1, tmp2.second}});
                upd[tmp2.first].push_back({1, {i+1, tmp2.second}});
                upd[tmp1.first].push_back({1, {i+1, tmp1.second}});
                upd[tmp2.first].push_back({-1, {i+1, tmp1.second}});
            }
        }
        else
        {
            int x, y;
            cin >> x >> y;
            qry[x].push_back({++cnt, {i, y}});
        }
    }
    str.clear();
    s.clear();
    for (int i=1; i<=n; i++)
    {
        for (auto x:upd[i])
            vec.push_back({{1, x.first}, x.second});
        for (auto x:qry[i])
            vec.push_back({{0, x.first}, x.second});
        upd[i].clear();
        qry[i].clear();
    }
    recur(0, vec.size()-1);
    for (int i=1; i<=cnt; i++)
        cout << ans[i] << '\n';
}

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