Submission #1073723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073723		Hamed_Ghaffari	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	909 ms	68264 KiB

street_lamps

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

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int,int>;

#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back
#define Mp make_pair
#define mid ((l+r)>>1)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 3e5+5;
const int LOG = 20;

ll fen[MXN];
vector<pii> fen_his;
inline void updx(int p, int x, bool add=1) { 
    if(add) fen_his.pb(Mp(p, x));
    for(p+=2; p<MXN; p+=p&-p) fen[p] += x; 
}
inline ll getx(int p) {
    ll res=0;
    for(p+=2; p; p-=p&-p) res += fen[p];
    return res;
}
inline ll getr(int s, int e) { return getx(e)-getx(s-1); }
inline void roll() {
    while(SZ(fen_his)) {
        updx(fen_his.back().X, -fen_his.back().Y, 0);
        fen_his.pop_back();
    }
}

bool isq[MXN];
int n, q, ans[MXN];
string s;
vector<array<int, 4>> segs;

void dcq(int l, int r) {
    if(l>=r) return;
    dcq(l, mid);
    dcq(mid+1, r);
    int p0=l, p1=mid+1;
    vector<array<int, 4>> sorted;
    while(p0<=mid && p1<=r)
        if(segs[p0][2]<=segs[p1][2]) {
            sorted.pb(segs[p0++]);
            if(sorted.back()[0] == 0) updx(sorted.back()[3], sorted.back()[1]);
        }
        else {
            sorted.pb(segs[p1++]);
            if(sorted.back()[0] == 1)
                ans[sorted.back()[1]] += getr(sorted.back()[3], MXN-3);
        }
    while(p0<=mid) {
        sorted.pb(segs[p0++]);
        if(sorted.back()[0] == 0) updx(sorted.back()[3], sorted.back()[1]);
    }
    while(p1<=r) {
        sorted.pb(segs[p1++]);
        if(sorted.back()[0] == 1)
            ans[sorted.back()[1]] += getr(sorted.back()[3], MXN-3);
    }
    assert(SZ(sorted) == r-l+1);
    for(int i=l; i<=r; i++) segs[i] = sorted[i-l];
    roll();
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q >> s;
    s = '0' + s + '0';
    n += 2;
    set<int> st;
    for(int l=0,r=0; l<n; l=r)
        if(s[l]=='0') {
            st.insert(l);
            r++;
        }
        else {
            while(r<n && s[r] == '1') r++;
            segs.pb({0, -1, l, r-1});
        }
    for(int i=2; i<=q+1; i++) {
        string t;
        cin >> t;
        if(t == "query") {
            isq[i] = 1;
            int l, r;
            cin >> l >> r;
            segs.pb({1, i, l, r-1});
        }
        else {
            int p;
            cin >> p;
            if(s[p] == '0') {
                s[p] = '1';
                st.erase(p);
                int nxt = *st.lower_bound(p), pre = *--st.lower_bound(p);
                segs.pb({0, i, pre+1, p-1});
                segs.pb({0, i, p+1, nxt-1});
                segs.pb({0, -i, pre+1, nxt-1});
            }
            else {
                int nxt = *st.lower_bound(p), pre = *--st.lower_bound(p);
                segs.pb({0, i, pre+1, nxt-1});
                segs.pb({0, -i, pre+1, p-1});
                segs.pb({0, -i, p+1, nxt-1});
                s[p] = '0';
                st.insert(p);
            }
        }
    }
    dcq(0, SZ(segs)-1);
    for(int i=2; i<=q+1; i++)
        if(isq[i])
            cout << ans[i] + (ans[i]<0)*i << '\n';
    return 0;
}

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