Submission #1184389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184389		byunjaewoo	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	3048 ms	277108 KiB

street_lamps

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

const int N=300010;
int n, q, a[N], ans[N];
array<int, 3> qry[N];
vector<array<int, 4>> vec;
map<pair<int, int>, int> mp;
string s;

class BIT {
public:
    void update(int k, int v) {
        for (int i=k; i<N; i+=i&-i) tree[i]+=v;
    }
    void update(int l, int r, int v) {
        update(l, v), update(r+1, -v);
    }
    int query2(int k) {
        int ret=0;
        for (int i=k; i>=1; i-=i&-i) ret+=tree[i];
        return ret;
    }
    int query(int l, int r) {
        return query2(r)-query2(l-1);
    }
    pair<int, int> query(int k) {
        pair<int, int> ret={k, k};
        for (int s=1, e=k-1; s<=e; ) {
            int m=(s+e)/2;
            if (query(m, k-1)==k-m) ret.first=m, e=m-1;
            else s=m+1;
        }
        for (int s=k+1, e=n; s<=e; ) {
            int m=(s+e)/2;
            if (query(k+1, m)==m-k) ret.second=m, s=m+1;
            else e=m-1;
        }
        return ret;
    }
private:
    int tree[N];
}T, T1, T2;

void upd(int l, int r, int t, int v) {
    if (v) mp[{l, r}]=t;
    else {
        vec.push_back({mp[{l, r}], t-1, l, r}), mp.erase({l, r});
    }
}

void dnc(int l, int r, vector<array<int, 4>> &vec) {
    if (r<=l) return;
    int m=(l+r)/2;
    vector<array<int, 4>> vecl, vecr;
    vector<array<int, 4>> v, v2;
    for (auto [tl, tr, x, y]:vec) {
        if (tl<=l && r<=tr) {
            v2.push_back({x, x, y, 1});
            v2.push_back({y+1, x, y, -1});
        }
        else {
            if (min(tr, m)-max(tl, l)+1>0) {
                v.push_back({x, x, y, min(tr, m)-max(tl, l)+1});
                v.push_back({y+1, x, y, -(min(tr, m)-max(tl, l)+1)});
            }
            if (tl<=m) vecl.push_back({tl, tr, x, y});
            if (tr>m) vecr.push_back({tl, tr, x, y});
        }
    }
    sort(v.begin(), v.end());
    vector<array<int, 3>> qryv, qryv1;
    for (int i=m+1; i<=r; i++) if (qry[i][0]) qryv.push_back({qry[i][1], qry[i][2], i});
    for (int i=l; i<=r; i++) if (qry[i][0]) qryv1.push_back({qry[i][1], qry[i][2], i});
    sort(qryv.begin(), qryv.end()), sort(qryv1.begin(), qryv1.end());
    sort(v.begin(), v.end()), sort(v2.begin(), v2.end());
    int j=0, k=0;
    for (int i=0; i<qryv.size(); i++) {
        while (j<v.size() && v[j][0]<=qryv[i][0]) T.update(v[j][1], v[j][2], v[j][3]), j++;
        ans[qryv[i][2]]+=T.query2(qryv[i][1]);
    }
    for (int i=0; i<qryv1.size(); i++) {
        while (k<v2.size() && v2[k][0]<=qryv1[i][0]) T1.update(v2[k][1], v2[k][2], v2[k][3]), k++;
        ans[qryv1[i][2]]+=T1.query2(qryv1[i][1])*(qryv1[i][2]-l);
    }
    while (j<v.size()) T.update(v[j][1], v[j][2], v[j][3]), j++;
    while (k<v2.size()) T1.update(v2[k][1], v2[k][2], v2[k][3]), k++;
    dnc(l, m, vecl), dnc(m+1, r, vecr);
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin>>n>>q>>s;
    for (int i=1; i<=n; i++) {
        a[i]=s[i-1]-'0';
        if (a[i]) T2.update(i, 1);
    }
    for (int i=1, l=0; i<=n+1; i++) {
        if (i>n || !a[i]) {
            if (l) upd(l, i-1, 0, 1);
            l=0;
        }
        else if (!l) l=i;
    }
    for (int i=1; i<=q; i++) {
        string s; cin>>s;
        if (s=="query") {
            qry[i][0]=1;
            cin>>qry[i][1]>>qry[i][2];
            qry[i][2]--;
        }
        else {
            cin>>qry[i][1];
            int k=qry[i][1];
            auto [l, r]=T2.query(k);
            upd(l, r, i, 1-a[k]);
            if (l<k) upd(l, k-1, i, a[k]);
            if (k<r) upd(k+1, r, i, a[k]);
            a[k]^=1;
            T2.update(k, 2*a[k]-1);
        }
    }
    while (!mp.empty()) upd(mp.begin()->first.first, mp.begin()->first.second, q, 0);
    dnc(0, q, vec);
    for (int i=1; i<=q; i++) if (qry[i][0]) cout<<ans[i]<<"\n";
    return 0;
}

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