Submission #719867

#	Time	Username	Problem	Language	Result	Execution time	Memory
719867		badont	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	1945 ms	69008 KiB

street_lamps

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <array>
#include <set>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define pb push_back
#define all(x) x.begin(),x.end()

template<typename T>
struct fen {
	vector<T> tr;
	ll mxn;

	fen(ll sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(ll g, T k) {
    g++;
		assert(g > 0);
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(ll g) {
    g++;
		T res = 0;
		for (; g > 0; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(ll l, ll r) { 
    if (l > r) return T(0);
    return ge(r) - ge(l - 1); 
  }
};

void solve() {
  ll n, q; cin >> n >> q;
  string input_string; cin >> input_string;

  vector<ll> a(n);
  for (int i = 0; i < n; i++) a[i] = input_string[i] - '0';

  // x, y, delta, idx, multiplier
  using query_t = array<ll, 5>; 
  ll chain = 0;
  set<pii> gang;
  for (int i = 0; i < n; i++) {
    if (a[i]) { chain++; }
    else {
      if (chain) {
        gang.insert({i - chain, i - 1});
      }
      chain = 0;
    }
  } 
  if (chain) gang.insert({n - chain, n - 1});

  vector<query_t> queries;
  for (const auto& [x, y] : gang) {
    queries.pb({x, y, 0, -1, 1});
  }
  
  constexpr ll INF = 1e18;

  for (int q_idx = 1; q_idx <= q; q_idx++) {
    string s; cin >> s;
    if (s == "query") {
      ll l, r;
      cin >> l >> r;
      l--; r--; r--;

      // start < l + 1, end > r - 1
      queries.pb({l + 1, r - 1, -1, q_idx, 1});
    } else {
      ll x; cin >> x; x--;
      if (a[x] == 1) {
        // splitttter
        auto geq = gang.lower_bound({x, INF});
        assert(geq != gang.begin());
        geq = prev(geq);
        
        auto [l, r] = *geq; gang.erase(geq);
        assert(l <= x and r >= x);
        queries.pb({l, r, q_idx, -1, -1});
        if (l < x) {
          gang.insert({l, x - 1});
          queries.pb({l, x - 1, q_idx, -1, 1});
        } 
        if (r > x) {
          gang.insert({x + 1, r});
          queries.pb({x + 1, r, q_idx, -1, 1});
        }
      } else {
        // uniter!
        ll l_under = -1, r_under = -1, l_above = -1, r_above = -1;
        if (x > 0 and a[x - 1] == 1) {
          assert(gang.lower_bound({x, x}) != gang.begin());
          auto iter = prev(gang.lower_bound({x, x}));
          l_under = (*iter).first, r_under = (*iter).second;
          assert(l_under < x and r_under < x and l_under <= r_under);
          queries.pb({l_under, r_under, q_idx, -1, -1});
          gang.erase(iter);
        }

        if (x < n - 1 and a[x + 1] == 1) {
          auto iter = gang.lower_bound({x, x});
          assert(iter != gang.end());
          l_above = (*iter).first, r_above = (*iter).second;
          assert(l_above > x and r_above > x and l_above <= r_above);
          queries.pb({l_above, r_above, q_idx, -1, -1});
          gang.erase(iter);
        }

        ll new_l = x, new_r = x;
        if (l_under != -1) new_l = l_under;
        if (r_above != -1) new_r = r_above;
        gang.insert({new_l, new_r});
        queries.pb({new_l, new_r, q_idx, -1, 1});
      }
      a[x] ^= 1;
    }

    #ifdef LOCAL
      cout << "current gang: \n";
      for (auto& [x, y] : gang) {
        cout << x << " " << y << "\n";
      }
      for (auto& u : a) cout << u; cout << '\n';
    #endif
  }

  vector<bool> v(q + 1);
  vector<ll> ans(q + 1);
  fen<ll> tree_pos(n), tree_neg(n);
  fen<ll> tree_count(n);

  #ifdef LOCAL
    cout << "current gang: \n";
    for (auto& [x, y] : gang) {
      cout << x << " " << y << "\n";
    }

    cout << "queries: \n";
    for (auto& [l, r, delta, idx, multiplier] : queries)
      cout << l << " " << r << ' ' << delta << ' ' << idx << ' ' << multiplier << "\n";
  #endif


  auto dfs = [&](auto& dfs, ll l, ll r) -> void {
    if (l == r) return;
    ll m = (l + r) / 2;
    dfs(dfs, l, m);
    dfs(dfs, m + 1, r);

    vector<ll> l_idx(m - l + 1), r_idx(r - m);
    iota(all(l_idx), l); iota(all(r_idx), m + 1);
    sort(all(l_idx), [&](ll i, ll j) {
      return queries[i] < queries[j];
    });
    sort(all(r_idx), [&](ll i, ll j) {
      return queries[i] < queries[j];
    });
    ll next_left_ptr = 0;
    vector<array<ll, 3>> upds;
    for (const auto& q_idx : r_idx) {
      const auto& [l, r, delta, idx, multiplier] = queries[q_idx];
      while (next_left_ptr < (int)l_idx.size()) {
        const auto& o = l_idx[next_left_ptr];
        if (queries[o][0] >= l) break;
        const auto [px, py, pdelta, pidx, pmult] = queries[o];

        if (pidx == -1) {
          assert(pdelta != -1);
          if (pmult == -1) {
            tree_neg.upd(py, pdelta);
            tree_count.upd(py, -1);
          } else {
            tree_pos.upd(py, pdelta);
            tree_count.upd(py, 1);
          }
          upds.pb({py, pdelta, pmult});
        }
        next_left_ptr++;
      }
      // with r greater
      if (idx != -1) {
        assert(delta == -1);
        ll from_count = idx * tree_count.rng(r + 1, n - 1);
        #ifdef LOCAL
        cout << idx << " " << from_count << '\n';
        #endif
        ll res = from_count - tree_pos.rng(r + 1, n - 1) + tree_neg.rng(r + 1, n - 1);
        ans[idx] += res;
        v[idx] = true;
      }
    }

    for (auto& [idx, delta, mult] : upds) {
      if (mult == -1) {
        tree_neg.upd(idx, -delta);
        tree_count.upd(idx, 1);
      } else {
        tree_pos.upd(idx, -delta);
        tree_count.upd(idx, -1);
      }
    }
  };

  dfs(dfs, 0, (int)queries.size() - 1);
  for (int i = 1; i <= q; i++) if (v[i]) {
    cout << ans[i] << '\n';
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:69:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |   for (const auto& [x, y] : gang) {
      |                    ^
street_lamps.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |         auto [l, r] = *geq; gang.erase(geq);
      |              ^
street_lamps.cpp: In lambda function:
street_lamps.cpp:176:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |       const auto& [l, r, delta, idx, multiplier] = queries[q_idx];
      |                   ^
street_lamps.cpp:180:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  180 |         const auto [px, py, pdelta, pidx, pmult] = queries[o];
      |                    ^
street_lamps.cpp:208:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |     for (auto& [idx, delta, mult] : upds) {
      |                ^

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