Submission #874151

#	Time	Username	Problem	Language	Result	Execution time	Memory
874151		abczz	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	854 ms	135112 KiB

street_lamps

#include <iostream>
#include <map>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

vector <ll> V;
vector <array<ll, 4>> Q;
map <ll, array<ll, 2> > mp;
array <ll, 2> bit[300001];
vector <ll> U;
ll n, q, a, b, t, F[300001];

void update(ll x, array<ll, 2> y) {
  while (x <= n) {
    U.push_back(x);
    bit[x] = {bit[x][0]+y[0], bit[x][1]+y[1]};
    x += x&-x;
  }
}

array<ll, 2> query(ll x) {
  array<ll, 2> ret = {0, 0};
  while (x) {
    ret = {ret[0]+bit[x][0], ret[1]+bit[x][1]};
    x -= x&-x;
  }
  return ret;
}

bool ok;
string S, T;

void cdq(ll l, ll r) {
  if (l == r) return;
  vector <array<ll, 4> > tmp;
  ll mid = (l+r)/2, i = l, j = mid+1;
  cdq(l, mid);
  cdq(mid+1, r);
  while (i <= mid && j <= r) {
    if (Q[i][1] <= Q[j][1]) {
      tmp.push_back(Q[i]);
      if (!Q[i][0]) {
        ++i;
        continue;
      }
      if (Q[i][0] == 1) update(n-Q[i][2], {1, -Q[i][3]});
      else update(n-Q[i][2], {-1, Q[i][3]});
      ++i;
    }
    else {
      tmp.push_back(Q[j]);
      if (Q[j][0]) {
        ++j;
        continue;
      }
      auto [x, y] = query(n-Q[j][2]);
      F[Q[j][3]] += y + x * Q[j][3];
      ++j;
    }
  }
  while (i <= mid) {
    tmp.push_back(Q[i]);
    ++i;
  }
  while (j <= r) {
    tmp.push_back(Q[j]);
    if (Q[j][0]) {
      ++j;
      continue;
    }
    auto [x, y] = query(n-Q[j][2]);
    F[Q[j][3]] += y + x * Q[j][3];
    ++j;
  }
  for (auto x : U) bit[x] = {0, 0};
  U.clear();
  j = 0;
  for (i=l; i<=r; ++i) {
    swap(Q[i], tmp[j++]);
  }
}

int main() {
  cin >> n >> q >> S;
  V.push_back(0);
  for (int i=0; i+1<S.length(); ++i) {
    if (S[i] != S[i+1]) V.push_back(i+1);
  }
  for (int i=0; i<V.size(); ++i) {
    if (S[V[i]] == '0') continue;
    if (i == V.size()-1) mp[V[i]] = {n-1, 0};
    else mp[V[i]] = {V[i+1]-1, 0};
  }
  while (q--) {
    ++t;
    F[t] = -1;
    cin >> T >> a;
    if (T == "toggle") {
      --a;
      ok = 0;
      if (S[a] == '0') {
        S[a] = '1';
        auto it = mp.lower_bound(a);
        if (it != mp.begin()) {
          auto pv = prev(it);
          if (pv->second[0] == a-1 && it != mp.end() && a+1 == it->first) {
            Q.push_back({1, pv->first, pv->second[0], pv->second[1]});
            Q.push_back({2, pv->first, pv->second[0], t});
            Q.push_back({1, it->first, it->second[0], it->second[1]});
            Q.push_back({2, it->first, it->second[0], t});
            auto r = it->second[0];
            mp.erase(it);
            mp[pv->first] = {r, t};
            ok = 1;
          }
          else if (pv->second[0] == a-1) {
            Q.push_back({1, pv->first, pv->second[0], pv->second[1]});
            Q.push_back({2, pv->first, pv->second[0], t});
            mp[pv->first] = {a, t};
            ok = 1;
          }
        }
        if (ok) continue;
        if (it != mp.end() && a+1 == it->first) {
          Q.push_back({1, it->first, it->second[0], it->second[1]});
          Q.push_back({2, it->first, it->second[0], t});
          auto r = it->second[0];
          mp.erase(it);
          mp[a] = {r, t};
        }
        else mp[a] = {a, t};
      }
      else {
        S[a] = '0';
        auto it = prev(mp.lower_bound(a+1));
        Q.push_back({1, it->first, it->second[0], it->second[1]});
        Q.push_back({2, it->first, it->second[0], t});
        if (it->first == a && it->second[0] == a) mp.erase(it);
        else if (it->first == a) {
          auto r = it->second[0];
          mp.erase(it);
          mp[a+1] = {r, t};
        }
        else if (it->second[0] == a) mp[it->first] = {a-1, t};
        else {
          auto r = it->second[0];
          mp[it->first] = {a-1, t};
          mp[a+1] = {r, t};
        }
      }
    }
    else {
      F[t] = 0;
      cin >> b;
      --a, b -= 2;
      Q.push_back({0, a, b, t});
    }
  }
  for (auto [x, y] : mp) {
    Q.push_back({1, x, y[0], y[1]});
  }
  sort(Q.begin(), Q.end(), [](auto a, auto b) {
    return a[3] < b[3] || (a[3] == b[3] && a[0] > b[0]);
  });
  cdq(0, Q.size()-1);
  for (int i=1; i<=t; ++i) {
    if (F[i] >= 0) cout << F[i] << '\n';
  }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void cdq(long long int, long long int)':
street_lamps.cpp:60:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |       auto [x, y] = query(n-Q[j][2]);
      |            ^
street_lamps.cpp:75:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     auto [x, y] = query(n-Q[j][2]);
      |          ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for (int i=0; i+1<S.length(); ++i) {
      |                 ~~~^~~~~~~~~~~
street_lamps.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
street_lamps.cpp:95:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     if (i == V.size()-1) mp[V[i]] = {n-1, 0};
      |         ~~^~~~~~~~~~~~~
street_lamps.cpp:163:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |   for (auto [x, y] : mp) {
      |             ^

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