oj.uz

Submission #855824

# Submission time Handle Problem Language Result Execution time Memory
855824 2023-10-02T01:30:37 Z NeroZein Street Lamps (APIO19_street_lamps) C++17
0 / 100
 1 ms 604 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int INF = 1e9; 

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  set<array<int, 3>> se; 
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') {
      continue;
    }
    int j = i;
    while (j + 1 < n && s[j + 1] == '1') {
      j++; 
    }
    se.insert({i, j, 0}); 
    i = j; 
  }
  auto edit_set = [&](int i, int t) {
    if (s[i] == '1') {
      array<int, 3> key = {i, INF, INF};
      auto f = se.upper_bound(key);
      --f;
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        int l = (*f)[0], r = (*f)[1];
        se.erase(f); 
        se.insert({l, i - 1, t});
        se.insert({i + 1, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        int l = (*f)[0];
        se.erase(f);
        se.insert({l, i - 1, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        int r = (*f)[1];
        se.erase(f);
        se.insert({i + 1, r, t}); 
      }
    } else {
      if (i > 0 && i < n - 1 && s[i - 1] == '1' && s[i + 1] == '1') {
        array<int, 3> key = {i, -1, -1}; 
        auto pr = se.upper_bound(key);
        --pr;
        key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        int l = (*pr)[0], r = (*nx)[1];
        se.erase(pr);
        se.erase(nx);
        se.insert({l, r, t}); 
      } else if (i > 0 && s[i - 1] == '1') {
        array<int, 3> key = {i, -1, -1}; 
        auto pr = se.upper_bound(key);
        int l = (*pr)[0], r = i; 
        se.erase(pr); 
        se.insert({l, r, t}); 
      } else if (i < n - 1 && s[i + 1] == '1') {
        array<int, 3> key = {i, INF, INF}; 
        auto nx = se.upper_bound(key);
        int l = i, r = (*nx)[1];
        se.insert({l, r, t}); 
      } else {
        se.insert({i, i, t}); 
      }
    }
    s[i] ^= 1; 
  }; 
  vector<vector<pair<int, int>>> vec(n);
  for (int i = 1; i <= q; ++i) {
    string qs;
    cin >> qs;
    if (qs == "query") {
      int l, r;
      cin >> l >> r;
      --l, r -= 2; 
      int ans = 0; 
      array<int, 3> key = {l, INF, INF}; 
      auto f = se.upper_bound(key);
      if (f != se.begin()) {
        --f; 
        if ((*f)[0] <= l && (*f)[1] >= r) {
          ans += i - (*f)[2];
        }
      }
      cout << ans << '\n'; 
    } else {
      int ind;
      cin >> ind;
      edit_set(ind - 1, i); 
    }
  }
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -