Submission #255859

#	Time	Username	Problem	Language	Result	Execution time	Memory
255859		balbit	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	536 ms	36400 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 3e5+5;

//vector<pii> g[maxn];
bool hi[maxn];
int ps[maxn];
int ans[maxn], lt[maxn];

struct ty{
    int l, r, need, id;
};

struct grp{
    int l, r;
    vector<ty> v;
};

int s[maxn];

int QU(int e) {
//    bug(e);C
    int re = 0;
    for (++e; e>0; e -= e&-e) re += s[e];
    return re;
}

void MO(int e, int v) {
    if (e == -1) return;
    for (++e; e<maxn; e+=e&-e) s[e] += v;
}

signed main(){
    IOS();
    int n,q; cin>>n>>q;

    for (int i = 0; i<n; ++i) {
        char c; cin>>c;
        hi[i] = c=='1';
        if (hi[i]) {
            lt[i] = -1;
        }
        ps[i+1] = ps[i] + hi[i];
    }
    vector<pii> chg;
    grp org = {-1,q+1, {}};
    for (int i = 0; i<q; ++i) {
        string s; cin>>s;
        if (s[0] == 'q') {
            int a,b; cin>>a>>b; --a; --b; --b;
            org.v.pb({a,b,(b-a+1)-(ps[b+1] - ps[a]), i});
            bug(org.v.back().need);
        }else{
            int x; cin>>x;
            chg.pb({i,x-1});

        }
    }
    chg.pb({q+1000, -1});
    vector<int> ans(q,-2);

    queue<grp> qq;
    qq.push(org);
//    set<int> hv;
    int now = 0;
    while (!qq.empty()){
        grp g = qq.front(); qq.pop();
        bug(g.l, g.r);
        if (g.l == g.r) {
            for (auto x : g.v) {
                ans[x.id] = g.l;
            }
            continue;
        }
        int mid = (g.l + g.r+2)/2-1;
        if (chg[now].f > mid) {
            now = 0; memset(s, 0, sizeof s);
        }
        while (chg[now].f <= mid) {
            bug("HI");
            MO(chg[now].s,1); ++now;
        }
        grp tol = {g.l,mid,{}}, tor = {mid+1,g.r,{}};
        for (auto x : g.v) {
            bug("hmmmm");
            int btw = QU(x.r) - QU(x.l-1);
            if (btw >= x.need) tol.v.pb(x);
            else tor.v.pb(x);
        }
        bug("enddd");
        if (!tol.v.empty())
            qq.push(tol);
        if (!tor.v.empty())
            qq.push(tor);
    }
    for (int i = 0; i<q; ++i) {
        if (ans[i] != -2) {
            cout<<max(0,i-ans[i])<<endl;
        }
    }
}

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