Submission #466855

#	Time	Username	Problem	Language	Result	Execution time	Memory
466855		thomas_li	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3592 ms	83620 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
template <class T, class IndexType> struct OfflineSemiSparseFenwickTree2D {
  static_assert(is_integral<IndexType>::value, "IndexType must be integeral");
  int N; vector<int> st, cnt; vector<IndexType> inds; vector<T> BIT;
  int getInd(int i, IndexType j) {
    return upper_bound(inds.begin() + st[i], inds.begin() + st[i] + cnt[i], j)
        - inds.begin() - st[i];
  }
  OfflineSemiSparseFenwickTree2D(int N,
                                 vector<pair<int, IndexType>> updateInds)
      : N(N), st(N + 1, 0), cnt(N + 1, 0) {
    sort(updateInds.begin(), updateInds.end(),
         [&] (const pair<int, IndexType> &a, const pair<int, IndexType> &b) {
      return a.second < b.second;
    });
    vector<IndexType> last(N + 1, IndexType());
    for (auto &&u : updateInds) for (int i = u.first + 1; i <= N; i += i & -i)
      if (cnt[i] == 0 || u.second != last[i]) { cnt[i]++; last[i] = u.second; }
    for (int i = 1; i <= N; i++) st[i] = st[i - 1] + cnt[i - 1];
    inds.resize(st[N] + cnt[N]); BIT.resize(st[N] + cnt[N]);
    fill(cnt.begin(), cnt.end(), 0); for (auto &&u : updateInds)
      for (int i = u.first + 1; i <= N; i += i & -i)
        if (cnt[i] == 0 || u.second != inds[st[i] + cnt[i] - 1])
          inds[st[i] + cnt[i]++] = u.second;
  }
  void update(int i, IndexType j, T v) {
    for (i++; i <= N; i += i & -i)
      for (int s = st[i], c = cnt[i], y = getInd(i, j); y <= c; y += y & -y)
        BIT[s + y - 1] += v;
  }
  T query(int d, IndexType r) {
    T ret = T(); for (d++; d > 0; d -= d & -d)
      for (int s = st[d], y = getInd(d, r); y > 0; y -= y & -y)
        ret += BIT[s + y - 1];
    return ret;
  }
  T query(int d, IndexType l, IndexType r) {
    return query(d, r) - query(d, l - 1);
  }
  T query(int u, int d, IndexType l, IndexType r) {
    return query(d, l, r) - query(u - 1, l, r);
  }
};
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q; cin >> n >> q;
    string s,ts; cin >> s;
    ts = s;
    vector<pi> upd_inds;
    auto fake_upd = [&](int x1, int x2, int y1, int y2){
        upd_inds.emplace_back(x2+1,y2+1);   
        upd_inds.emplace_back(x1,y1);
        upd_inds.emplace_back(x2+1,y1);
        upd_inds.emplace_back(x1,y2+1);
    };
    auto fake_add = [&](int l, int r){
        fake_upd(l,r,l,r);
    };
    set<pi> in;
    vector<vector<array<int,3>>> to_add(q+1);
    for(int i = 0; i < n; i++){
        if(s[i] == '0') continue;
        int ptr = i;
        while(ptr < n && s[ptr] == '1') ptr++;
        // all intervals (l,r) where i <= l,r < ptr will be affected
        to_add[q].push_back({0,i,ptr-1});     
        fake_add(i,ptr-1); in.insert({i,ptr-1});
        i = ptr-1; 
    }
    vector<array<int,3>> qu; vector<bool> sub(q);
    for(int i = 0; i < q; i++){
        string t; cin >> t;
        if(t == "toggle"){
            int x; cin >> x; x--;
            qu.push_back({0,x,0});
            if(s[x] == '0'){
                // merge left and right intervals (if exists) 
                auto rit = in.lower_bound({x,-1});
                int l = x, r = x; bool fl = 0;
                if(rit != in.end() && rit->first == x+1){
                    to_add[i].push_back({1,rit->first,rit->second});
                    r = rit->second; fl = 1; //fake_add(rit->first,rit->second);
                }
                if(rit != in.begin()){
                    auto lft = rit; lft--;
                    if(lft->second == x-1){
                        l = lft->first;
                        //fake_add(lft->first,lft->second);
                        to_add[i].push_back({1,lft->first,lft->second});
                        in.erase(lft);                     }
                }
                if(fl){
                    // erase rit
                    in.erase(in.lower_bound({x,-1}));
                }
                in.insert({l,r});
                fake_add(l,r);
                to_add[i].push_back({0,l,r});
            } else{
                auto cur = in.upper_bound({x,x});  
                if(cur == in.end() || cur->first > x || x > cur->second) cur--;
                auto[l,r] = *cur;
                assert(l <= x && x <= r);
                to_add[i].push_back({1,l,r});
                in.erase(cur); //fake_add(l,r);
                if(l < x){
                    in.insert({l,x-1});
                    fake_add(l,x-1);
                    to_add[i].push_back({0,l,x-1});
                } 
                if(x < r){
                    in.insert({x+1,r});
                    fake_add(x+1,r);
                    to_add[i].push_back({0,x+1,r});
                }
            }
            s[x] = (s[x] == '0' ? '1' : '0');
        } else{
            int a,b; cin >> a >> b;
            a--; b-=2;
            qu.push_back({1,a,b}); bool fl = 0;
            auto cur = in.upper_bound({a,a});
            if(cur == in.end() || cur->first > a || a > cur->second){
                if(cur == in.begin()) fl = 1;
                else cur--;
            }
            if(!fl){
                auto[l,r] = *cur;
                if(l <= a && b <= r) sub[i] = 1;
            } else sub[i] = 0;
        }
    }
    OfflineSemiSparseFenwickTree2D<int,int> ft(n+1,upd_inds);
    auto upd = [&](int x1, int x2, int y1, int y2, int v){
        if(x2 + 1 < n && y2 + 1 < n) ft.update(x2+1,y2+1,v);
        ft.update(x1,y1,v);
        if(x2 + 1 < n)ft.update(x2+1,y1,-v);
        if(y2 + 1 < n)ft.update(x1,y2+1,-v);
    };
    for(auto[t,l,r]:to_add[q]) upd(l,r,l,r,q);
    for(int i = 0; i < q; i++){
        auto add = [&](int l, int r){
            upd(l,r,l,r,q-i-1);   
        };
        auto rmv = [&](int l, int r){
            upd(l,r,l,r,-(q-i-1));        
        };
        if(qu[i][0] == 0){
            for(auto[t,l,r]:to_add[i]){
                if(t == 0) add(l,r);
                else rmv(l,r);
            } 
        } else{
            int a = qu[i][1],b = qu[i][2];
            cout << ft.query(a,b)-sub[i]*(q-i-1) << "\n";
        }
    }

}
// x coordinate is left endpoint, y coordinate is right endpoint

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