oj.uz

Submission #1044936

# Submission time Handle Problem Language Result Execution time Memory
1044936 2024-08-05T14:50:40 Z MercubytheFirst Street Lamps (APIO19_street_lamps) C++17
40 / 100
 294 ms 8676 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 4672 KB Output is correct
2 Correct 162 ms 4692 KB Output is correct
3 Correct 162 ms 4688 KB Output is correct
4 Correct 163 ms 7396 KB Output is correct
5 Correct 187 ms 7728 KB Output is correct
6 Correct 134 ms 7140 KB Output is correct
7 Correct 286 ms 7144 KB Output is correct
8 Correct 294 ms 8676 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 171 ms 4672 KB Output is correct
9 Correct 162 ms 4692 KB Output is correct
10 Correct 162 ms 4688 KB Output is correct
11 Correct 163 ms 7396 KB Output is correct
12 Correct 187 ms 7728 KB Output is correct
13 Correct 134 ms 7140 KB Output is correct
14 Correct 286 ms 7144 KB Output is correct
15 Correct 294 ms 8676 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -