oj.uz

Submission #719874

# Submission time Handle Problem Language Result Execution time Memory
719874 2023-04-07T00:03:51 Z badont Street Lamps (APIO19_street_lamps) C++17
0 / 100
 1876 ms 69220 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--;
      assert(l <= 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 0 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 1178 ms 34396 KB Output is correct
2 Correct 1138 ms 34620 KB Output is correct
3 Correct 1133 ms 35076 KB Output is correct
4 Correct 1426 ms 53504 KB Output is correct
5 Correct 1553 ms 53964 KB Output is correct
6 Correct 1486 ms 62828 KB Output is correct
7 Incorrect 736 ms 27236 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 584 KB Output is correct
3 Correct 3 ms 456 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1723 ms 62212 KB Output is correct
6 Correct 1751 ms 64548 KB Output is correct
7 Correct 1548 ms 51704 KB Output is correct
8 Correct 789 ms 28724 KB Output is correct
9 Correct 340 ms 14732 KB Output is correct
10 Correct 372 ms 21096 KB Output is correct
11 Correct 369 ms 20984 KB Output is correct
12 Incorrect 726 ms 27236 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 915 ms 40668 KB Output is correct
6 Correct 1193 ms 51248 KB Output is correct
7 Correct 1474 ms 62504 KB Output is correct
8 Correct 1876 ms 69220 KB Output is correct
9 Correct 1237 ms 39868 KB Output is correct
10 Correct 1472 ms 50008 KB Output is correct
11 Correct 1227 ms 39788 KB Output is correct
12 Correct 1469 ms 49984 KB Output is correct
13 Correct 1228 ms 39808 KB Output is correct
14 Correct 1472 ms 50048 KB Output is correct
15 Incorrect 716 ms 27364 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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