oj.uz

Submission #307707

# Submission time Handle Problem Language Result Execution time Memory
307707 2020-09-29T07:21:57 Z noclever Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 30568 KB 
#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( ) {
    memset(c, 0, sizeof(int) * MAXF);
  }
}
 
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++) {
    queries[i] = sorted_queries[i];
  }
 
  BIT::clear();
  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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 8 ms 1664 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct
5 Correct 9 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 16416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 1912 KB Output is correct
2 Correct 79 ms 1664 KB Output is correct
3 Correct 67 ms 1664 KB Output is correct
4 Correct 47 ms 1664 KB Output is correct
5 Execution timed out 5054 ms 30568 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1664 KB Output is correct
2 Correct 60 ms 1664 KB Output is correct
3 Correct 75 ms 1664 KB Output is correct
4 Correct 93 ms 1664 KB Output is correct
5 Execution timed out 5041 ms 25224 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 8 ms 1664 KB Output is correct
4 Correct 8 ms 1536 KB Output is correct
5 Correct 9 ms 1536 KB Output is correct
6 Correct 6 ms 1536 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Execution timed out 5061 ms 16416 KB Time limit exceeded
9 Halted 0 ms 0 KB -