Submission #1203893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203893		Hanksburger	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	954 ms	589824 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, ind=1, cnt;
set<pair<int, int> > s;
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)
{
    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)
        update(i->lc, ql, qr, x);
    if (mid<qr && ql<=i->r)
        update(i->rc, ql, qr, x);
    i->seg=i->lc->seg+i->rc->seg;
}
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->l<=qr && ql<=mid)
        ans+=query(i->lc, ql, qr);
    if (mid<qr && ql<=i->r)
        ans+=query(i->rc, ql, qr);
    return ans;
}
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, 1, x.second.first);
    }
    recur(l, mid);
    recur(mid+1, r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string str;
    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}});
        }
    }
    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});
    }
    recur(0, vec.size()-1);
    for (int i=1; i<=cnt; i++)
        cout << ans[i] << '\n';
}

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