oj.uz

Submission #1095057

# Submission time Handle Problem Language Result Execution time Memory
1095057 2024-10-01T08:10:41 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1215 ms 524288 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;

struct Query {
  int x, y;
};

std::string s;

std::set<int> lt;

Query Q[NMAX + 1];
int answer[NMAX + 1];

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

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

int n;

void finish(int l, int t) {
  events.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 (pos != rt[me]) {
      lt.insert(pos + 1);
      rt[pos + 1] = rt[me];
      tt[pos + 1] = t;
    }
    if (me == pos) {
      lt.erase(pos);
    } else {
     rt[me] = pos - 1;
      tt[me] = t;
    }
  }
}

void query(int l, int r, int t) {
  events.push_back({l, r, -(t + 1)});
  int me = *std::prev(lt.upper_bound(l));
  if (me != -1 && rt[me] >= r) {
    answer[t] += t - tt[me];
  }
}

std::vector<int> ys[NMAX + 1];
std::vector<ll> aib[NMAX + 1];
void updateDry(int x, int y, int v = 0) {
  for (; x <= NMAX; x += x & -x) {
    ys[x].push_back(y);
  }
}
void queryDry(int x, int y) {
  for (; x > 0; x -= x & -x) {
    ys[x].push_back(y);
  }
}
void build() {
  for (int i = 1; i <= NMAX; i++) {
    ys[i].push_back(0);
    ys[i].push_back(NMAX + 1);
    std::sort(ys[i].begin(), ys[i].end());
    ys[i].erase(std::unique(ys[i].begin(), ys[i].end()), ys[i].end());
    aib[i].resize((int) ys[i].size() + 1, 0);
  }
}

void updateWet(int x, int y, int v) {
  for (; x <= NMAX; x += x & -x) {
    for (int j = std::lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin(); j > 0; j -= j & -j) {
      aib[x][j] += v;
    }
  }
}
int queryWet(int x, int y) {
  int ret = 0;
  for (; x > 0; x -= x & -x) {
    for (int j = std::lower_bound(ys[x].begin(), ys[x].end(), y) - ys[x].begin(); j <= (int) ys[x].size(); j += j & -j) {
      ret += aib[x][j];
    }
  }
  return ret;
}

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 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") {
      std::cin >> Q[i].x;
      Q[i].y = -1;
      answer[i] = -1;
      toggle(Q[i].x, i);
    } else {
      std::cin >> Q[i].x >> Q[i].y;
      Q[i].y--;
      answer[i] = 0;
      query(Q[i].x, Q[i].y, i);
    }
  }
  
  for (const auto &[l, r, t] : events) {
    if (t >= 0) { // update
      updateDry(l, r, t);
    } else { // query
      queryDry(l, r);
    }
  }

  build();

  for (const auto &[l, r, t] : events) {
    if (t >= 0) {
      // std::cout << "update " << l << ' ' << r << ' ' << t << '\n';
      updateWet(l, r, t);
    } else {
      answer[-(t + 1)] += queryWet(l, r);
    }
  }

  for (int i = 1; i <= q; i++) {
    if (answer[i] != -1) {
      std::cout << answer[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 Runtime error 407 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 484 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33444 KB Output is correct
2 Correct 39 ms 33360 KB Output is correct
3 Correct 41 ms 33368 KB Output is correct
4 Correct 43 ms 33616 KB Output is correct
5 Correct 794 ms 77944 KB Output is correct
6 Correct 1014 ms 88208 KB Output is correct
7 Correct 1105 ms 102056 KB Output is correct
8 Correct 1192 ms 155756 KB Output is correct
9 Correct 127 ms 46016 KB Output is correct
10 Correct 136 ms 47044 KB Output is correct
11 Correct 135 ms 47540 KB Output is correct
12 Correct 653 ms 79272 KB Output is correct
13 Correct 1215 ms 155684 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 33500 KB Output is correct
2 Incorrect 49 ms 33312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 407 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -