oj.uz

Submission #719867

# Submission time Handle Problem Language Result Execution time Memory
719867 2023-04-06T23:02:14 Z badont Street Lamps (APIO19_street_lamps) C++14
0 / 100
 1945 ms 69008 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});
        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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 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 1165 ms 34260 KB Output is correct
2 Correct 1189 ms 34648 KB Output is correct
3 Correct 1166 ms 34908 KB Output is correct
4 Correct 1496 ms 53368 KB Output is correct
5 Correct 1579 ms 53840 KB Output is correct
6 Correct 1601 ms 62732 KB Output is correct
7 Incorrect 738 ms 27160 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 4 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1814 ms 61964 KB Output is correct
6 Correct 1920 ms 64244 KB Output is correct
7 Correct 1678 ms 51444 KB Output is correct
8 Correct 869 ms 28444 KB Output is correct
9 Correct 325 ms 14644 KB Output is correct
10 Correct 390 ms 20932 KB Output is correct
11 Correct 335 ms 20928 KB Output is correct
12 Incorrect 823 ms 27008 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 3 ms 596 KB Output is correct
5 Correct 981 ms 40556 KB Output is correct
6 Correct 1306 ms 51032 KB Output is correct
7 Correct 1602 ms 62376 KB Output is correct
8 Correct 1945 ms 69008 KB Output is correct
9 Correct 1404 ms 39672 KB Output is correct
10 Correct 1540 ms 49996 KB Output is correct
11 Correct 1306 ms 39620 KB Output is correct
12 Correct 1479 ms 49884 KB Output is correct
13 Correct 1231 ms 39736 KB Output is correct
14 Correct 1497 ms 49964 KB Output is correct
15 Incorrect 701 ms 27132 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 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -