Submission #1143854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143854		aykhn	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1805 ms	288928 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

struct BIT
{
  int n;
  vector<int> ft;
  void init(int N)
  {
    n = N + 1;
    ft.assign(n + 1, 0);
  }
  void add(int pos, int val)
  {
    for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
  }
  int get(int pos, int res = 0)
  {
    for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
    return res;
  }
};

const int MXN = 3e5 + 5;

int n;
int arr[MXN];
vector<array<int, 2>> ls[MXN];
vector<array<int, 3>> q1[MXN];
int L[MXN], wh[MXN];
set<int> rs;
vector<int> mp[MXN << 2];
BIT st[MXN << 2];

void addtomap(int l, int r, int x, int ind, int val)
{
  mp[x].push_back(val);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (ind <= mid) addtomap(l, mid, 2*x, ind, val);
  else addtomap(mid + 1, r, 2*x + 1, ind, val);
}
int getind(vector<int> &mp, int ind)
{
  return upper_bound(mp.begin(), mp.end(), ind) - mp.begin() - 1;
}
void upd(int l, int r, int x, int ind, int A, int B)
{
  st[x].add(getind(mp[x], A), B);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (ind <= mid) upd(l, mid, 2*x, ind, A, B);
  else upd(mid + 1, r, 2*x + 1, ind, A, B);
}
int get(int l, int r, int x, int lx, int rx, int ind)
{
  if (l > rx || r < lx) return 0;
  if (l >= lx && r <= rx) return st[x].get(getind(mp[x], ind));
  int mid = (l + r) >> 1;
  return get(l, mid, 2*x, lx, rx, ind) + get(mid + 1, r, 2*x + 1, lx, rx, ind);
}

void rem(int R, int T)
{
  addtomap(1, n, 1, R, L[R]);
  q1[T - 1].push_back({R, L[R], T - wh[R]});
  rs.erase(R);
  L[R] = -1;
}
void add(int R, int lx, int T)
{
  L[R] = lx;
  wh[R] = T;
  rs.insert(R);
}

signed main()
{
  ios_base::sync_with_stdio(0); 
  cin.tie(0);
  fill(L, L + MXN, -1);
  int q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++)
  {
    char ch;
    cin >> ch;
    arr[i] = ch - '0';
  }
  int prv = -1;
  for (int i = 1; i <= n; i++)
  {
    if (arr[i] == 1 && (i == 1 || arr[i - 1] == 0)) prv = i;
    if (arr[i] == 1 && (i == n || arr[i + 1] == 0)) add(i, prv, 1);
  }
  vector<array<int, 2>> qq(q + 1, {-1, -1});
  vector<int> ans(q + 1, 0);
  for (int t = 1; t <= q; t++)
  {
    string s;
    cin >> s;
    if (s == "toggle")
    {
      int i;
      cin >> i;
      if (arr[i] == 0)
      {
        auto it = rs.lower_bound(i);
        int lx = i, rx = i;
        if (it != rs.end() && L[*it] == i + 1) 
        {
          rx = *it;
          rem(*it, t + 1);
        }
        it = rs.lower_bound(i);
        if (it != rs.begin() && *prev(it) == i - 1) 
        {
          lx = L[*prev(it)];
          rem(*prev(it), t + 1);
        }
        add(rx, lx, t + 1);
      }
      else
      {
        auto it = rs.lower_bound(i);
        int l1 = L[*it], r1 = i - 1, l2 = i + 1, r2 = *it;
        rem(*it, t + 1);
        if (l1 <= r1) add(r1, l1, t + 1);
        if (l2 <= r2) add(r2, l2, t + 1);
      }
      arr[i] ^= 1;
    }
    else
    {
      int l, r, res = 0;
      cin >> l >> r;
      r--;
      qq[t] = {l, r};
      auto it = rs.lower_bound(r);
      if (it != rs.end())
      {
        if (L[*it] <= l) ans[t] += (t + 1) - wh[*it];
      }
    }
  }
  for (int i = 1; i < (MXN << 2); i++)
  {
    mp[i].push_back(-inf);
    mp[i].push_back(inf);
    sort(mp[i].begin(), mp[i].end());
    mp[i].resize(unique(mp[i].begin(), mp[i].end()) - mp[i].begin());
    st[i].init(mp[i].size());
  }
  for (int t = 1; t <= q; t++)
  {
    for (auto &i : q1[t]) upd(1, n, 1, i[0], i[1], i[2]);
    if (qq[t][0] != -1)
    {
      ans[t] += get(1, n, 1, qq[t][1], n, qq[t][0]);
      cout << ans[t] << '\n';
    }
  }
}

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