oj.uz

Submission #1044937

# Submission time Handle Problem Language Result Execution time Memory
1044937 2024-08-05T14:50:53 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
40 / 100
 298 ms 8672 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 348 KB Output is correct
2 Correct 1 ms 344 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 4688 KB Output is correct
2 Correct 171 ms 4692 KB Output is correct
3 Correct 162 ms 4904 KB Output is correct
4 Correct 163 ms 7396 KB Output is correct
5 Correct 196 ms 7724 KB Output is correct
6 Correct 142 ms 7144 KB Output is correct
7 Correct 295 ms 7140 KB Output is correct
8 Correct 298 ms 8672 KB Output is correct

Subtask #3
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 #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 348 KB Output is correct
2 Correct 1 ms 344 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 Correct 154 ms 4688 KB Output is correct
9 Correct 171 ms 4692 KB Output is correct
10 Correct 162 ms 4904 KB Output is correct
11 Correct 163 ms 7396 KB Output is correct
12 Correct 196 ms 7724 KB Output is correct
13 Correct 142 ms 7144 KB Output is correct
14 Correct 295 ms 7140 KB Output is correct
15 Correct 298 ms 8672 KB Output is correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -