Submission #603816

#	Time	Username	Problem	Language	Result	Execution time	Memory
603816		OttoTheDino	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5097 ms	94068 KiB

street_lamps

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 3e5;
int ans[mx+1], ft[mx+1];
vector<vi> events;

//O(n log n) easily achievable with merge-sort???

namespace BIT {
    void upd (int x, int id) {
        for (;id<=mx;id+=id&(-id)) ft[id] += x;
    }
    int qry (int id) {
        int res = 0;
        for (;id;id-=id&(-id)) res += ft[id];
        return res;
    }
}

//important part begins:
void cdq (int l, int r) {

    if (l==r) return;

    int mid = (l+r)/2;
    cdq (l, mid);
    cdq (mid+1, r);

    //sort in increasing order of x use BIT afterwards clear BIT
    //remember that ys are inverted in events

    sort(events.begin()+l, events.begin()+r+1);

    vii undo;
    rep (i,l,r) {
        int y = events[i][1], id = events[i][2], delt = events[i][3], t = events[i][4];
        if (t>mid) ans[id] += BIT::qry(y);
        else {
            BIT::upd(delt,y);
            undo.pb({delt,y});
        }
    }
    for (ii el : undo) BIT::upd(-el.fi, el.se);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >> n >> q;

    bool b[n+1]; 
    string s; cin >> s;

    set<int> st;
    st.insert(0);
    st.insert(n+1);

    rep (i,1,n) {
        b[i] = s[i-1]-'0';
        if (!b[i]) st.insert(i);
    }

    vi get;
    rep (i,1,q) {
        string tp; cin >> tp;
        int t = len(events);
        if (tp[0]=='t') {
            int u; cin >> u;
            int prv = *--st.lower_bound(u)+1, nxt = *st.upper_bound(u)-1, c = 2*b[u]-1;
                events.pb({prv,u,0,c*i,t++}); 
            if (u+1<=mx)
                events.pb({u+1,u,0,-c*i,t++});
            if (nxt+1<=mx)
                events.pb({prv,(nxt+1),0,-c*i,t++});
            if (max(u+1,nxt+1)<=mx)
                events.pb({u+1,(nxt+1),0,c*i,t++});
            if (b[u]) st.insert(u);
            else st.erase(u);
            b[u] ^= 1;
        }
        else {
            int x, y; cin >> x >> y;
            --y;
            get.pb(i);
            if (*st.lower_bound(x)>y) ans[i] += i;
            events.pb({x,y,i,0,t++});
        }
    }

    cdq(0,len(events)-1);

    for (int el : get) cout << ans[el] << "\n";

    return 0;
}

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