Submission #1203950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203950		Hanksburger	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	3702 ms	110840 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;
set<pair<int, int> > s;
string str;
struct node
{
    node *lc, *rc;
    int l, r;
    pair<int, int> val;
    node(int l, int r) : lc(0), rc(0), l(l), r(r), val({0, 0}) {}
};
void update(node *i, int x, int y, int z)
{
    if (i->l==i->r)
    {
        i->val.first+=y;
        i->val.second+=z;
        return;
    }
    int mid=(i->l+i->r)/2;
    if (x<=mid)
    {
        if (!i->lc)
            i->lc=new node(i->l, mid);
        update(i->lc, x, y, z);
    }
    else
    {
        if (!i->rc)
            i->rc=new node(mid+1, i->r);
        update(i->rc, x, y, z);
    }
    i->val={(i->lc?i->lc->val.first:0)+(i->rc?i->rc->val.first:0), (i->lc?i->lc->val.second:0)+(i->rc?i->rc->val.second:0)};
}
pair<int, int> query(node *i, int ql, int qr)
{
    if (ql<=i->l && i->r<=qr)
        return i->val;
    int mid=(i->l+i->r)/2;
    pair<int, int> ans={0, 0};
    if (i->lc && i->l<=qr && ql<=mid)
    {
        pair<int, int> res=query(i->lc, ql, qr);
        ans.first+=res.first;
        ans.second+=res.second;
    }
    if (i->rc && mid<qr && ql<=i->r)
    {
        pair<int, int> res=query(i->rc, ql, qr);
        ans.first+=res.first;
        ans.second+=res.second;
    }
    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.first!=y.second.first)
        return x.second.first<y.second.first;
    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]);
        int sz=v.size();
        for (int i=mid+1; i<=r; i++)
            if (!vec[i].first.first)
                v.push_back(vec[i]);
        if (v.size()<=100)
        {
            for (int i=0; i<sz; i++)
                for (int j=sz; j<v.size(); j++)
                    ans[v[j].first.second]+=(v[i].second.second>=v[j].second.second)*max(0, v[j].second.first-v[i].second.first+1)*v[i].first.second;
        }
        else
        {
            sort(v.begin(), v.end(), cmp);
            node *root=new node(1, n+1);
            for (auto x:v)
            {
                if (x.first.first)
                    update(root, x.second.second, x.second.first*x.first.second, x.first.second);
                else
                {
                    pair<int, int> res=query(root, x.second.second, n+1);
                    ans[x.first.second]+=(x.second.first+1)*res.second-res.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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20