Submission #926124

#	Time	Username	Problem	Language	Result	Execution time	Memory
926124		myst6	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	3103 ms	524288 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Node;
struct Node2;

const int s1 = 15'000'000;
const int s2 = 500'000;

vector<Node> node(s1); int next1 = 1;
vector<Node2> node2(s2); int next2 = 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) {
    if (v < xl || v > xr) return;
    val.first += add;
    val.second += 1;
    if (xl != xr) {
      int xm = (xl + xr) / 2;
      if (v <= xm) {
        if (!left) left = next1++;
        node[left].update(v, xl, xm, add);
      } else {
        if (!right) right = next1++;
        node[right].update(v, xm+1, xr, add);
      }
    }
  }
  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;
    }
  }
};

struct Node2 {
  int left, right;
  int val;
  Node2() : left(0), right(0), val(0) {}
  void update(int v, int w, int xl, int xr, int add) {
    if (v < xl || v > xr) return;
    if (!val) val = next1++;
    node[val].update(w, 0, n-1, add);
    if (xl != xr) {
      int xm = (xl + xr) / 2;
      if (v <= xm) {
        if (!left) left = next2++;
        node2[left].update(v, w, xl, xm, add);
      } else {
        if (!right) right = next2++;
        node2[right].update(v, w, xm+1, xr, add);
      }
    }
  }
  pair<ll,int> query(int l1, int r1, int l2, int r2, int xl, int xr) {
    if (l1 > r1) return {0, 0};
    if (l1 == xl && r1 == xr) {
      return node[val].query(l2, r2, 0, n-1);
    } else {
      pair<ll,int> ans = {0, 0};
      int xm = (xl + xr) / 2;
      if (left) {
        pair<ll,int> leftans = node2[left].query(l1, min(r1, xm), l2, r2, xl, xm);
        ans.first += leftans.first;
        ans.second += leftans.second;
      }
      if (right) {
        pair<ll,int> rightans = node2[right].query(max(l1, xm+1), r1, l2, r2, xm+1, xr);
        ans.first += rightans.first;
        ans.second += rightans.second;
      }
      return ans;
    }
  }
};

// lamp turns on => at most 2 segments destryod and 1 segment added
// lamp turns off => 1 segment destroyed and at most 2 segments added
// count number of x=<a ^ y>=b
// (t,a,b,1) => a and b were connected at t
// (t,a,b,-1) => a and b were disconnected at t
// now for each query, just need to find sum of t of a1<=a2, b2>=b1, t1<t2
// and if the number of '1' events is one less thaan the '-1' events, 
// pretend there's (t2,a,b,-1)

// O(10^6) updates and O(5*10^5) queries, might not be fast enough.



int main() {
  int q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<array<int,2>> segments;
  vector<array<int,3>> queries;
  vector<array<int,4>> updates;
  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});
    }
  }
  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;
      queries.push_back({t, a-1, b-2});
    }
  }
  Node2 on, off;
  for (array<int,4> upd : updates) {
    if (upd[3] == -1) {
      off.update(upd[1], upd[2], 0, n-1, upd[0]);
    } else {
      on.update(upd[1], upd[2], 0, n-1, upd[0]);
    }
  }
  sort(queries.begin(), queries.end());
  for (array<int,3> qur : queries) {
    pair<ll,int> pOff = off.query(0, qur[1], qur[2], n-1, 0, n-1);
    pair<ll,int> pOn = on.query(0, qur[1], qur[2], n-1, 0, n-1);
    ll offSum = pOff.first;
    ll onSum = pOn.first;
    if (pOn.second > pOff.second) offSum += qur[0];
    // cout << qur[0] << "," << qur[1] << "," << qur[2] << "\n";
    // cout << pOff.first << "," << pOff.second << "\n";
    // cout << pOn.first << "," << pOn.second << "\n";
    // cout << offSum << "," << onSum << "\n";
    cout << max(0LL, offSum - onSum) << "\n";
  }
  return 0;
}

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