Submission #926168

#	Time	Username	Problem	Language	Result	Execution time	Memory
926168		myst6	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2422 ms	79608 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Node;

const int s1 = 2'000'000;

vector<Node> node(s1); int next1 = 1;

int n;

struct Node {
  int left, right;
  pair<ll,int> val;
  Node() : left(0), right(0), val({0,0}) {}
  void update(int v, int xl, int xr, int add, int ct) {
    if (v < xl || v > xr) return;
    val.first += add;
    val.second += ct;
    if (xl != xr) {
      int xm = (xl + xr) / 2;
      if (v <= xm) {
        if (!left) left = next1++;
        node[left].update(v, xl, xm, add, ct);
      } else {
        if (!right) right = next1++;
        node[right].update(v, xm+1, xr, add, ct);
      }
    }
  }
  pair<ll,int> query(int l, int r, int xl, int xr) {
    if (l > r) return {0, 0};
    if (l == xl && r == xr) {
      return val;
    } else {
      pair<ll,int> ans = {0, 0};
      int xm = (xl + xr) / 2;
      if (left) {
        pair<ll,int> leftans = node[left].query(l, min(r, xm), xl, xm);
        ans.first += leftans.first;
        ans.second += leftans.second;
      }
      if (right) {
        pair<ll,int> rightans = node[right].query(max(l, xm+1), r, xm+1, xr);
        ans.first += rightans.first;
        ans.second += rightans.second;
      }
      return ans;
    }
  }
};


// count {t1<t2, a1<a2+1, b1>b2-1} for each query
// because of equality, updates must be processed before queries
Node onTree, offTree;
vector<array<int,5>> updates;
vector<ll> offSum, onSum;
vector<int> offCount, onCount;
void cdq(int l, int r) {
  if (l == r) return;
  int m = (l + r) / 2;
  cdq(l, m); cdq(m+1, r);
  sort(updates.begin() + l, updates.begin() + m + 1, 
    [&](array<int,5> A, array<int,5> B) -> bool {
      return A[1] < B[1];
  });
  sort(updates.begin() + m + 1, updates.begin() + r + 1,
    [&](array<int,5> A, array<int,5> B) -> bool {
      return A[1] < B[1];
  });
  stack<pair<int,int>> offActions, onActions;
  int a = l, b = m+1;
  while (a <= m || b <= r) {
    bool isleft;
    int cur;
    if (a > m || (b <= r && updates[b][1] <= updates[a][1])) cur = b++, isleft = 0;
    else cur = a++, isleft = 1;
    if (updates[cur][3] == -1 && isleft) {
      offTree.update(updates[cur][2], 0, n-1, updates[cur][0], +1);
      offActions.push({updates[cur][2], updates[cur][0]});
    } else if (updates[cur][3] == 1 && isleft) {
      onTree.update(updates[cur][2], 0, n-1, updates[cur][0], +1);
      onActions.push({updates[cur][2], updates[cur][0]});
    } else if (updates[cur][3] == 0 && !isleft) {
      int qi = updates[cur][4];
      pair<ll,int> onDat = onTree.query(updates[cur][2]+1, n-1, 0, n-1);
      onSum[qi] += onDat.first; onCount[qi] += onDat.second; 
      pair<ll,int> offDat = offTree.query(updates[cur][2]+1, n-1, 0, n-1);
      offSum[qi] += offDat.first; offCount[qi] += offDat.second; 
    }
  }
  while (offActions.size()) {
    offTree.update(offActions.top().first, 0, n-1, -offActions.top().second, -1);
    offActions.pop();
  }
  while (onActions.size()) {
    onTree.update(onActions.top().first, 0, n-1, -onActions.top().second, -1);
    onActions.pop();
  }
}

int main() {
  int q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<array<int,2>> segments;
  for (int i=0; i<n; i++) {
    if (s[i] == '1') {
      int l = i;
      while (i < n-1 && s[i+1] == '1') i++;
      segments.insert({l, i});
      updates.push_back({0, l, i, +1});
    }
  }
  int qc = 0;
  vector<int> qtime;
  for (int t=1; t<=q; t++) {
    string type;
    cin >> type;
    if (type == "toggle") {
      int i;
      cin >> i;
      i--;
      if (s[i] == '0') {
        int l = i, r = i;
        auto right = segments.lower_bound({i, i});
        if (right != segments.end() && right->at(0) == i+1) {
          r = right->at(1);
          updates.push_back({t, i+1, r, -1});
          segments.erase(right);
        }
        auto left = segments.lower_bound({i, i});
        if (left != segments.begin()) --left;
        if (left != segments.end() && left->at(1) == i-1) {
          l = left->at(0);
          updates.push_back({t, l, i-1, -1});
          segments.erase(left);
        }
        segments.insert({l, r});
        updates.push_back({t, l, r, +1});
        s[i] = '1';
      } else {
        auto it = prev(segments.lower_bound({i+1, i+1}));
        int l = it->at(0), r = it->at(1);
        segments.erase(it);
        updates.push_back({t, l, r, -1});
        if (l < i) {
          segments.insert({l, i-1});
          updates.push_back({t, l, i-1, +1});
        }
        if (r > i) {
          segments.insert({i+1, r});
          updates.push_back({t, i+1, r, +1});
        }
        s[i] = '0';
      }
    } else {
      int a, b;
      cin >> a >> b;
      updates.push_back({t, a, b-3, 0, qc++});
      qtime.push_back(t);
    }
  }
  sort(updates.begin(), updates.end());
  offSum.resize(qc); onSum.resize(qc);
  offCount.resize(qc); onCount.resize(qc); 
  cdq(0, (int) updates.size() - 1);
  for (int i=0; i<qc; i++) {
    ll ans = offSum[i] - onSum[i];
    if (onCount[i] > offCount[i]) ans += qtime[i];
    cout << ans << "\n";
  }
  return 0;
}

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