Submission #307712

#	Time	Username	Problem	Language	Result	Execution time	Memory
307712		noclever	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1476 ms	39612 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
 
#define MAX_QUERY_NUMBER 600005
#define MAXF 300005
#define QUERY_OPT  0
#define UPDATE_OPT 1
#define DUMMY 0
 
struct Query {
  // type == QUERY_OPT: query for ans indexed at extra, val is not relevent;
  // type == UPDATE_OPT: update with val for [y, extra).
  int x, y, val, type, extra;  
};
 
Query queries[MAX_QUERY_NUMBER];
Query sorted_queries[MAX_QUERY_NUMBER];
 
int ans[MAXF];
 
inline int lowbit( int num ) { return num&(-num); }
namespace BIT { 
  int c[MAXF] = {0};
  void add( int x, int v ) {
    for( ; x <= MAXF-1; x += lowbit(x) ) {
      c[x] += v;
    }
  }
  
  int query( int x ) {
    int sum = 0;
    for( ; x; x -= lowbit(x) ) {
      sum += c[x];
    }
    return sum;
  }

  void clear(int x) {
    for( ; x <= MAXF-1; x += lowbit(x) ) {
      c[x] = 0;
    }
  }
}
 
void solve(int l, int r) {
  if (r - l <= 1) return;
  int m = (l + r) / 2;
  solve(l, m);
  solve(m, r);
 
  int p = l, q = m, t = l;
  while (p < m && q < r) {
    if (queries[p].x <= queries[q].x) {
      if (queries[p].type == UPDATE_OPT) {
        BIT::add(queries[p].y, queries[p].val);
        BIT::add(queries[p].extra, - queries[p].val);
      }
      sorted_queries[t++] = queries[p];
      p++;
    } else {
      if (queries[q].type == QUERY_OPT) {
        ans[queries[q].extra] += BIT::query(queries[q].y);
      }
      sorted_queries[t++] = queries[q];
      q++;
    }
  }
 
  while (q < r) {
    if (queries[q].type == QUERY_OPT) {
      ans[queries[q].extra] += BIT::query(queries[q].y);
    }
    sorted_queries[t++] = queries[q];
    q++;    
  }
 
  while (p < m) {
    sorted_queries[t++] = queries[p++];
  }
  
  for (int i = l; i < r; i++) {
    if (queries[i].type == UPDATE_OPT) {
      BIT::clear(queries[i].y);
      BIT::clear(queries[i].extra);
    }
    queries[i] = sorted_queries[i];
  }
 
  return;
}
 
struct comp {
  inline bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second < b.second;
  }
};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;  
  cin >> n >> q;
  set< pair<int, int>, comp> st;
  for (int i = 1; i <= n + 1; i++) {
    st.insert({i, i});
  }
  string s;
  cin >> s;
  for (int i = 1; i <= n; i++) {
    if (s[i - 1] == '1') {
      auto it = st.upper_bound({0, i});
      pair<int, int> tmp = {prev(it)->first, it->second};
      st.erase(prev(it)); st.erase(it);
      st.insert(tmp);
    }
  }
 
  int idx = 0, ans_number = 0;
 
  for (int cur = 1; cur <= q; cur++) {
    string t;
    cin >> t;
    if (t == "query") {
      int l, r;
      cin >> l >> r;
      
      if (st.lower_bound({0, l}) == st.lower_bound({0, r})) {
        ans[ans_number] += cur;
      }
      queries[idx++] = (Query){l, r, DUMMY, QUERY_OPT, ans_number++};
 
    } else {
      int x;
      cin >> x;
      int i_1, j_1, i_2, j_2;
      int val = cur;
      if (s[x - 1] == '1') {
        auto it = st.lower_bound({0, x});
        i_1 = it->first;
        j_1 = x + 1;
        i_2 = x;
        j_2 = it->second;
        pair<int, int> tmp_1 = {it->first, x}, tmp_2 = {x + 1, it->second};
        st.erase({it->first, it->second});
        st.insert(tmp_1); st.insert(tmp_2);
        s[x - 1] = '0';
      } else {
        auto it = st.upper_bound({0, x});
        i_1 = prev(it)->first, i_2 = prev(it)->second, j_1 = it->first, j_2 = it->second;
        pair<int, int> tmp = {i_1, j_2};
        val = - val; 
        st.erase({i_1, i_2}); st.erase({j_1, j_2});
        st.insert(tmp);
        s[x - 1] = '1';
      }      
      queries[idx++] = Query{i_1, j_1, val, UPDATE_OPT, j_2 + 1};
      queries[idx++] = Query{i_2 + 1, j_1, - val, UPDATE_OPT, j_2 + 1};     
    }
  }
 
  solve(0, idx);
  for (idx = 0; idx < ans_number; idx ++ ) {
    cout << ans[idx] << "\n";
  }
 
  return 0;
}

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