Submission #982534

#	Time	Username	Problem	Language	Result	Execution time	Memory
982534		Tuanlinh123	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5074 ms	50976 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> H[maxn], Q[maxn];
ll a[maxn], last[maxn], answer[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, q; 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);}
    }
    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) H[i].pb({j?upd[i][j-1]+1:1, upd[i][j]});
    }
    for (ll i=1; i<=n; i++)
    {
        for (auto [l, r]:H[i])
            for (ll j=l; j<=r; j++)
                last[j]=i+1;
        for (auto [l, id]:Q[i])
            for (ll j=1; j<=id; j++)
                if (last[j]<=l) answer[id]++;
    }
    for (ll i=1; i<=q; i++)
        if (answer[i]>=0) cout << answer[i] << "\n";
}

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