Submission #1044936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044936		MercubytheFirst	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	294 ms	8676 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll mod = 1e9 + 7;
const ll N = 2e5 + 37;
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
const ll inf = (ll)1e9 + 37;

int n, Q;
string s;
void brute() {
  vector<string> a{s};
  while(Q--) {
    string qt;
    cin >> qt;
    if(qt == "toggle") {
      int i;
      cin >> i;
      --i;
      s[i] ^= 1;
    }
    else if(qt == "query") {
      int l, r;
      cin >> l >> r;
      --l, --r;
      int ans = 0;
      for(const string& b : a) {
        if(count(b.begin() + l, b.begin() + r, 0) == 0) {
          ++ans;
        }
      }
      cout << ans << endl;
    }
    else assert(false);
    a.push_back(s);
  }
}

void one_solve(const vector<array<int, 3>>& qs) {
  vector<int> ans(n), last(n);
  for(int qn = 1; qn <= Q; ++qn) {
    const auto& q = qs[qn - 1];
    if(q[0] == 1) {
      int i = q[1];
      if(s[i]) {
        ans[i] += qn - last[i];
      }
      last[i] = qn;
      s[i] ^= 1;
    }
    else if(q[0] == 0){
      int a = q[1];
      int cur = ans[a];
      if(s[a]) {
        cur += qn - last[a];
      }
      cout << cur << endl;
    }
    else assert(false);
  }
}

void solve() {
  cin >> n >> Q >> s;
  for(char& c : s) 
    c -= '0';
  if(n <= 100 and Q <= 100) {
    brute();
    return;
  }
  vector<array<int, 3>> qs(Q);
  bool one = true;
  for(int i = 0; i < Q; ++i) {
    string qt;
    cin >> qt;
    qs[i][0] = (qt == "toggle");
    if(qt == "toggle") {
      cin >> qs[i][1];
      --qs[i][1];
    }
    else {
      cin >> qs[i][1] >> qs[i][2];
      --qs[i][1], --qs[i][2];
      if(qs[i][2] - qs[i][1] != 1) {
        one = false;
      }
    }
  }
  if(one) {
    one_solve(qs);
  }
}


signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // signed t; cin >> t; while(t--) 
    solve();
}

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}
 
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& ST) {
  os << "{";
  for(auto x : ST)
    os << x << ", ";
  os << "} ";
  return os;
}

template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& ST) {
  os << "{";
  for(auto x : ST)
    os << x << ", ";
  os << "} ";
  return os;
}

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