oj.uz

Submission #1044932

# Submission time Handle Problem Language Result Execution time Memory
1044932 2024-08-05T14:48:17 Z MercubytheFirst Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 14572 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 * n * Q <= 1e7) {
    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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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
0 / 20.0

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

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 0 ms 344 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 Execution timed out 5036 ms 14572 KB Time limit exceeded
9 Halted 0 ms 0 KB -