Submission #982618

#	Time	Username	Problem	Language	Result	Execution time	Memory
982618		Tuanlinh123	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3302 ms	355424 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_RURQ
{
    ll n;
    vector <vector <ll>> pos, A, B, C, D; // a[x][y], a[x][y]*x, a[x][y]*y, a[x][y]*x*y
    BIT2D_RURQ (ll n): n(n) {pos=A=B=C=D=vector <vector <ll>> (n+1);}

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

    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());
            A[i]=B[i]=C[i]=D[i]=vector <ll> (sz(pos[i]), 0);
        }
    }

    void update(ll x, ll y, ll val)
    {
        for (ll i=x; i<=n; i+=i&(-i))
            for (ll j=lower_bound(pos[i].begin(), pos[i].end(), y)-pos[i].begin(); j<sz(pos[i]); j+=j&(-j))
                A[i][j]+=val, B[i][j]+=val*x, C[i][j]+=val*y, D[i][j]+=val*x*y;
    }
    void update(ll x, ll y, ll l, ll r, ll val) {update(x, l, val), update(x, r+1, -val), update(y+1, l, -val), update(y+1, r+1, val);}

    ll query(ll x, ll y)
    {
        ll a=0, b=0, c=0, d=0;
        for (ll i=x; i; i-=i&(-i))
            for (ll j=upper_bound(pos[i].begin(), pos[i].end(), y)-pos[i].begin()-1; j; j-=j&(-j))
                a+=A[i][j], b+=B[i][j], c+=C[i][j], d+=D[i][j];
        return a*(x+1)*(y+1)-b*(y+1)-c*(x+1)+d;
    }
};

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);
    }
    BIT2D_RURQ S(n);
    for (ll i=1; i<=n; i++)
        for (ll j=0; j<sz(U[i]); j++)
            S.fupdate(U[i][j].se.fi, U[i][j].se.fi, U[i][j].fi.fi, U[i][j].fi.se);
    S.build();
    for (ll i=1; i<=n; i++)
    {
        for (ll j=0; j<sz(U[i]); j++)
            S.update(U[i][j].se.fi, U[i][j].se.fi, U[i][j].fi.fi, U[i][j].fi.se, U[i][j].se.se);
        for (auto [l, id]:Q[i]) answer[id]=S.query(l, id);
    }
    for (ll i=1; i<=q; i++)
        if (answer[i]>=0) cout << answer[i] << " ";
}

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