Submission #1172447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172447		fryingduc	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	2991 ms	163048 KiB

street_lamps

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3e5 + 5;
int n, q;
int a[maxn];
char qo[maxn];
int ql[maxn], qr[maxn];

struct info {
  int l, r, x, y;
  
  info() {}
  
  info(int l, int r, int x, int y) : l(l), r(r), x(x), y(y) {}
};
vector<info> vec;

int szx;
vector<int> cpx;
vector<vector<int>> srg;
vector<vector<pair<long long, int>>> bit;
vector<array<int, 3>> que[maxn];

void update(int x, int y, int val, int dlt) {
  for (int i = x; i <= szx; i += i & (-i)) {
    int j = lower_bound(srg[i].begin(), srg[i].end(), n - y + 1) - srg[i].begin() + 1;
    for (; j < (int)bit[i].size(); j += j & (-j)) {
      bit[i][j].first += dlt * val;
      bit[i][j].second += dlt;
    }
  }
}

pair<int, int> get(int u, int v) {
  pair<long long, int> ans = make_pair(0, 0);
  for (int i = u; i > 0; i -= i & (-i)) {
    int j = upper_bound(srg[i].begin(), srg[i].end(), n - v + 1) - srg[i].begin();
    for (; j > 0; j -= j & (-j)) {
      ans.first += bit[i][j].first;
      ans.second += bit[i][j].second;
    }
  }
  return ans;
}

void solve() {
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    char c; cin >> c;
    a[i] = c - '0';
  }
  for (int i = 1; i <= q; ++i) {
    string op; cin >> op;
    qo[i] = op[0];
    if (op[0] == 't') {
      cin >> ql[i];
    } else {
      cin >> ql[i] >> qr[i];
    }
  }
  int prv = 0;
  set<array<int, 3>> s;
  set<int> zr;
  zr.insert(0);
  zr.insert(n + 1);
  for (int i = 1; i <= n + 1; ++i) {
    if (!a[i]) {
      zr.insert(i);
      s.insert({prv, i, 0});
      prv = i;
    }
  }
  for (int i = 1; i <= q; ++i) {
    if (qo[i] == 't') {
      int p = ql[i];
      int nr = *zr.upper_bound(p);
      int nl = *(--zr.lower_bound(p));
      if (!a[p]) {
        auto it = s.lower_bound({p, -1, -1});
        vec.emplace_back((*it)[0], (*it)[1], (*it)[2], i);
        it = s.erase(it), it--;
        vec.emplace_back((*it)[0], (*it)[1], (*it)[2], i);
        s.erase(it);
        s.insert({nl, nr, i});
        zr.erase(p);
      } else {
        auto it = --s.upper_bound({p, -1, -1});
        vec.emplace_back((*it)[0], (*it)[1], (*it)[2], i);
        s.erase(it);
        s.insert({nl, p, i});
        s.insert({p, nr, i});
        zr.insert(p);
      }
      a[p] ^= 1;
    }
  }
  for (auto vl : s) {
    vec.emplace_back(vl[0], vl[1], vl[2], q + 1);
  }
  for (auto [l, r, x, y] : vec) {
    cpx.push_back(l);
  }
  sort(cpx.begin(), cpx.end());
  cpx.erase(unique(cpx.begin(), cpx.end()), cpx.end());
  szx = (int)cpx.size();
  bit.resize(szx + 1);
  srg.resize(szx + 1);
  for (auto [l, r, x, y] : vec) {
    l = lower_bound(cpx.begin(), cpx.end(), l) - cpx.begin() + 1;
    for (int i = l; i <= szx; i += i & (-i)) {
      srg[i].push_back(n - r + 1);
    }
  } 
  for (int i = 1; i <= szx; ++i) {
    sort(srg[i].begin(), srg[i].end());
    srg[i].erase(unique(srg[i].begin(), srg[i].end()), srg[i].end());
    bit[i].resize((int)srg[i].size() + 2);
  }
  for (auto [l, r, x, y] : vec) {
    que[x].push_back({l, r, 1});
    que[y].push_back({l, r, -1});
  }
  for (int i = 0; i <= q; ++i) {
    if (i > 0 and qo[i] == 'q') {
      int u = ql[i] - 1, v = qr[i];
      u = upper_bound(cpx.begin(), cpx.end(), u) - cpx.begin();
      pair<long long, int> cur = get(u, v);
//      debug(i, u, qr[i], cur);
      cout << 1ll * i * cur.second - cur.first << '\n';
    }
    for (auto [u, v, dlt] : que[i]) {
      u = lower_bound(cpx.begin(), cpx.end(), u) - cpx.begin() + 1;
//      debug(i, u, v, dlt);
      update(u, v, i, dlt);
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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