Submission #982578

#	Time	Username	Problem	Language	Result	Execution time	Memory
982578		Tuanlinh123	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5014 ms	184040 KiB

street_lamps

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=300005;
vector <ll> upd[maxn];
vector <pll> Q[maxn];
ll n, q, a[maxn], answer[maxn];
vector <pair<pll, pll>> U[maxn];
ll cnt[maxn/100][maxn/100];

namespace intervals
{
    set <pair<pll, ll>> s;
    void init() {s.insert({{1, q}, 1}), U[1].pb({{1, q}, {1, 1}});}

    void add(ll l, ll r, ll t)
    {
        vector <pair<pll, ll>> sn;
        auto ptr=s.lower_bound(mp(mp(l, 0), 0));
        if (ptr!=s.begin()) ptr--;
        while (ptr!=s.end() && (*ptr).fi.fi<=r)
            sn.pb(*ptr), ptr=s.erase(ptr);
        s.insert({{l, r}, t+1}), U[t].pb({{l, r}, {t+1, 1}});
        for (ll i=0; i<sz(sn); i++)
        {
            ll L=sn[i].fi.fi, R=sn[i].fi.se, V=sn[i].se;
            if (R<l || L>r) s.insert({{L, R}, V});
            else if (l<=L && R<=r) U[t].pb({{L, R}, {V, -1}});
            else if (L<l && r<R) U[t].pb({{l, r}, {V, -1}}), s.insert({{L, l-1}, V}), s.insert({{r+1, R}, V});
            else if (L<l) U[t].pb({{l, R}, {V, -1}}), s.insert({{L, l-1}, V});
            else U[t].pb({{L, r}, {V, -1}}), s.insert({{r+1, R}, V});
        }
    }
} 

struct BIT2D
{
    ll n;
    vector <vector <ll>> pos, bit;
    BIT2D(ll n): n(n) {bit.resize(n+1);}

    void fupdate(ll x, ll y)
    {
        for (; x<=n; x+=x&(-x))
            pos[x].pb(y);
    }

    void build()
    {
        for (ll i=1; i<=n; i++)
        {
            pos[i].pb(0), sort(pos[i].begin(), pos[i].end());
            pos[i].resize(unique(pos[i].begin(), pos[i].end())-pos[i].begin());
            bit[i].assign(sz(pos[i]), 0);
        }
    }

    void update(ll x, ll y, ll val)
    {
        for (; x<=n; x+=x&(-x))
            for (ll j=lower_bound(pos[x].begin(), pos[x].end(), y)-pos[x].begin(); j<sz(pos[x]); j+=j&(-j))
                bit[x][j]+=val;
    }

    ll query(ll x, ll y)
    {
        ll ans=0;
        for (; x; x-=x&(-x))
            for (ll j=upper_bound(pos[x].begin(), pos[x].end(), y)-pos[x].begin()-1; j; j-=j&(-j))
                ans+=bit[x][j];
        return ans;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (ll i=1; i<=n; i++) {char c; cin >> c; a[i]=c=='1';}
    for (ll i=1; i<=q; i++) answer[i]=-1;
    for (ll i=1; i<=q; i++)
    {
        string t; cin >> t;
        if (t=="query") {ll l, r; cin >> l >> r, Q[r-1].pb({l, i}), answer[i]=0;}
        else {ll x; cin >> x, upd[x].pb(i);}
    }
    intervals::init();
    for (ll i=1; i<=n; i++)
    {
        upd[i].pb(q);
        for (ll j=0, s=a[i]; j<sz(upd[i]); j++, s^=1)
            if (!s) intervals::add(j?upd[i][j-1]+1:1, upd[i][j], i);
    }
    for (ll i=1; i<=n; i++)
    {
        for (ll j=0; j<sz(U[i]); j++)
            for (ll k=U[i][j].fi.fi; k<=U[i][j].fi.se; k++)
                cnt[U[i][j].se.fi][k]+=U[i][j].se.se;
        for (auto [l, id]:Q[i])
            for (ll j=1; j<=l; j++)
                for (ll k=1; k<=id; k++)
                    answer[id]+=cnt[j][k];
    }
    for (ll i=1; i<=q; i++)
        if (answer[i]>=0) cout << answer[i] << " ";
}

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