oj.uz

Submission #1095019

# Submission time Handle Problem Language Result Execution time Memory
1095019 2024-10-01T07:21:17 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
0 / 100
 5000 ms 16824 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <set>
#include <functional>
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const int INF = 1e9;
const int NMAX = 3e5;

std::string s;

std::set<int> lt;

int rt[NMAX + 1];
int tt[NMAX + 1];

std::vector<std::tuple<int, int, int>> collected;

void finish(int l, int t) {
  collected.push_back({l, rt[l], t - tt[l]});
  tt[l] = t;
}

void toggle(int pos, int t) {
  if (s[pos] == 0) {
    auto it = lt.lower_bound(pos);
    int st = *prev(it);
    int dr = *it;
    if (st != -1 && dr == pos + 1 && rt[st] == pos - 1) {    
      finish(st, t);
      finish(dr, t);
      lt.erase(dr);
      rt[st] = rt[dr];
    } else if (dr == pos + 1) {
      finish(dr, t);
      lt.erase(dr);
      lt.insert(pos);
      rt[pos] = rt[dr];
      tt[pos] = t;
    } else if (st != -1 && rt[st] == pos - 1) {
      finish(st, t);
      rt[st] = pos;
    } else {
      rt[pos] = pos;
      lt.insert(pos);
      tt[pos] = t;
    }
  } else {
    auto it = lt.upper_bound(pos);
    it = prev(it);
    auto me = *it;
    finish(me, t);
    if (me != rt[pos]) {
      lt.insert(pos + 1);
      rt[pos + 1] = rt[me];
      tt[pos + 1] = tt[me];
    }
    if (me == pos) {
      lt.erase(pos);
    } else {
      rt[me] = pos - 1;
    }
  }
}

int query(int l, int r, int t) {
  r--;
  int answer = 0;
  int me = *std::prev(lt.upper_bound(l));
  if (me != -1 && rt[me] >= r) {
    answer += t - tt[me];
  }
  for (const auto &[ll, rr, T] : collected) { 
    if (ll <= l && r <= rr) {
      answer += T;
    }
  }
  return answer;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int n, q;
  std::cin >> n >> q;

  std::cin >> s;
  s = '$' + s;

  lt.insert(-1);
  lt.insert(-2);
  lt.insert(n + 2);
  lt.insert(n + 3);
  
  for (int i = 1; i <= n; i++) {
    s[i] -= '0';
    if (s[i] == 1) {
      s[i] ^= 1;
      toggle(i, 0);
      s[i] ^= 1;
    }
  }

  for (int i = 1; i <= q; i++) {
    std::string type;
    std::cin >> type;
    if (type == "toggle") {
      int p;
      std::cin >> p;
      toggle(p, i);
      s[p] ^= 1;
    } else {
      int l, r;
      std::cin >> l >> r;
      std::cout << query(l, r, i) << '\n';
    }
  }

  return 0;
}

Compilation message

street_lamps.cpp:8:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    8 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1012 ms 16824 KB Output is correct
6 Execution timed out 5041 ms 10284 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Execution timed out 5058 ms 9184 KB Time limit exceeded
6 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 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -