oj.uz

Submission #719868

# Submission time Handle Problem Language Result Execution time Memory
719868 2023-04-06T23:05:16 Z badont Street Lamps (APIO19_street_lamps) C++17
0 / 100
 1905 ms 68936 KB 
#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) {
        assert(!gang.empty());
        // 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 + 69), tree_neg(n + 69);
  fen<ll> tree_count(n + 69);

  #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;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1166 ms 34292 KB Output is correct
2 Correct 1152 ms 34480 KB Output is correct
3 Correct 1194 ms 34852 KB Output is correct
4 Correct 1416 ms 53300 KB Output is correct
5 Correct 1463 ms 53624 KB Output is correct
6 Correct 1551 ms 62616 KB Output is correct
7 Incorrect 683 ms 27028 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1771 ms 62112 KB Output is correct
6 Correct 1809 ms 64192 KB Output is correct
7 Correct 1508 ms 51352 KB Output is correct
8 Correct 736 ms 28492 KB Output is correct
9 Correct 323 ms 14556 KB Output is correct
10 Correct 367 ms 20920 KB Output is correct
11 Correct 355 ms 20912 KB Output is correct
12 Incorrect 771 ms 27068 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 4 ms 568 KB Output is correct
5 Correct 1010 ms 40536 KB Output is correct
6 Correct 1310 ms 50912 KB Output is correct
7 Correct 1548 ms 62276 KB Output is correct
8 Correct 1905 ms 68936 KB Output is correct
9 Correct 1263 ms 39540 KB Output is correct
10 Correct 1561 ms 49784 KB Output is correct
11 Correct 1301 ms 39556 KB Output is correct
12 Correct 1527 ms 49760 KB Output is correct
13 Correct 1273 ms 39468 KB Output is correct
14 Correct 1522 ms 49796 KB Output is correct
15 Incorrect 768 ms 26976 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -