oj.uz

Submission #719855

# Submission time Handle Problem Language Result Execution time Memory
719855 2023-04-06T22:25:47 Z badont Street Lamps (APIO19_street_lamps) C++17
0 / 100
 1915 ms 73284 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) {
        // splitttter
        auto geq = gang.lower_bound({x, -INF});
        if ((*geq).first != x) {
          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) {
          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";
      }
    #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;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1166 ms 37480 KB Output is correct
2 Correct 1149 ms 38008 KB Output is correct
3 Correct 1151 ms 38784 KB Output is correct
4 Correct 1440 ms 58480 KB Output is correct
5 Correct 1559 ms 58968 KB Output is correct
6 Correct 1626 ms 67808 KB Output is correct
7 Incorrect 774 ms 33040 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1834 ms 65556 KB Output is correct
6 Correct 1848 ms 68056 KB Output is correct
7 Correct 1571 ms 55268 KB Output is correct
8 Correct 796 ms 32220 KB Output is correct
9 Correct 344 ms 17336 KB Output is correct
10 Correct 355 ms 23928 KB Output is correct
11 Correct 354 ms 24068 KB Output is correct
12 Incorrect 704 ms 30696 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 580 KB Output is correct
5 Correct 975 ms 46332 KB Output is correct
6 Correct 1213 ms 56340 KB Output is correct
7 Correct 1579 ms 67156 KB Output is correct
8 Correct 1915 ms 73284 KB Output is correct
9 Correct 1281 ms 42780 KB Output is correct
10 Correct 1539 ms 52696 KB Output is correct
11 Correct 1282 ms 42912 KB Output is correct
12 Correct 1497 ms 52756 KB Output is correct
13 Correct 1259 ms 42876 KB Output is correct
14 Correct 1672 ms 52716 KB Output is correct
15 Incorrect 809 ms 32988 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -