oj.uz

Submission #1095061

# Submission time Handle Problem Language Result Execution time Memory
1095061 2024-10-01T08:13:13 Z vjudge1 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1196 ms 149916 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) {
  if (l < 1) {
    return;
  }
  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 {
      assert(1 <= -(t + 1) && -(t + 1) <= q);
      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 Incorrect 40 ms 33240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 33364 KB Output is correct
2 Correct 37 ms 33372 KB Output is correct
3 Correct 39 ms 33332 KB Output is correct
4 Correct 54 ms 33836 KB Output is correct
5 Correct 764 ms 73640 KB Output is correct
6 Correct 937 ms 83624 KB Output is correct
7 Correct 1042 ms 96820 KB Output is correct
8 Correct 1175 ms 149740 KB Output is correct
9 Correct 126 ms 43196 KB Output is correct
10 Correct 127 ms 44048 KB Output is correct
11 Correct 145 ms 44272 KB Output is correct
12 Correct 665 ms 73384 KB Output is correct
13 Correct 1196 ms 149916 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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