oj.uz

Submission #917310

# Submission time Handle Problem Language Result Execution time Memory
917310 2024-01-27T17:53:21 Z duckindog Street Lamps (APIO19_street_lamps) C++14
20 / 100
 586 ms 63528 KB 
//from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
int n, q;
bool a[N];
struct Query {
  int ty, x, y;
  Query() : ty(0), x(0), y(0) {}
  Query(int ty, int x, int y) : ty(ty), x(x), y(y) {}
} Q[N];

int f[4 * N];
void build(int s, int l, int r) {
  if (l == r) {
    f[s] = (a[l] == 1 ? 0 : 1e8);
    return;
  }
  int mid = l + r >> 1;
  build(s * 2, l, mid); build(s * 2 + 1, mid + 1, r);
  f[s] = max(f[s * 2], f[s * 2 + 1]);
}
void update(int s, int l, int r, int x, int y) {
  if (y < l || y > r) return;
  if (l == r) {
    f[s] = x;
    return;
  }
  int mid = l + r >> 1;
  update(s * 2, l, mid, x, y); update(s * 2 + 1, mid + 1, r, x, y);
  f[s] = max(f[s * 2], f[s * 2 + 1]);
}
int query(int s, int l, int r, int u, int v) {
  if (v < l || u > r) return 0;
  if (u <= l && r <= v) return f[s];
  int mid = l + r >> 1;
  return max(query(s * 2, l, mid, u, v), query(s * 2 + 1, mid + 1, r, u, v));
}

vector<int> bit[N], vt[N];
void upd(int i, int j, int time) {
  for (; i; i -= i & -i) {
    if (!vt[i].size() || vt[i].back() < j) continue;
    auto p = lower_bound(vt[i].begin(), vt[i].end(), j) - vt[i].begin() + 1;
    for (int t = p; t <= vt[i].size(); t += t & -t) {
      bit[i][t] += max(0, time - query(1, 1, n, i, vt[i][t - 1]));
    }
  }

}

int que(int i, int j) {
  int ret = 0;
  for (; i <= n; i += i & -i) {

    auto p = lower_bound(vt[i].begin(), vt[i].end(), j) - vt[i].begin() + 1;
    for (int t = vt[i].size(); t; t -= t & -t) ret += bit[i][t];
  }
  return ret;
}


int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    char x; cin >> x;
    a[i] = (x == '1');
  }

  vector<pair<int, int>> querylist;
  for (int i = 1; i <= q; ++i) {
    string ty; cin >> ty;
    if (ty == "toggle") {
      int x; cin >> x;
      Q[i] = {0, x, 0};
    } else {
      int x, y; cin >> x >> y;
      querylist.push_back({x, y - 1});
      Q[i] = {1, x, y - 1};
    }
  }
  sort(querylist.begin(), querylist.end());
  querylist.resize(unique(querylist.begin(), querylist.end()) - querylist.begin());
  for (auto duck : querylist) {
    int x, y; tie (x, y) = duck;
    for (int i = x; i; i -= i & -i) vt[i].push_back(y);
  }
  for (int i = 1; i <= n; ++i) {
    sort(vt[i].begin(), vt[i].end());
    bit[i].resize(vt[i].size() + 1);
  }

  build(1, 1, n);

  for (int i = 1; i <= q; ++i) {
    int ty = Q[i].ty, x = Q[i].x, y = Q[i].y;
    if (!ty) {
      a[x] = 1 - a[x];
      if (a[x]) {
        update(1, 1, n, i, x);
      } else {
        upd(x, x, i);
        update(1, 1, n, 1e8, x);
      }
    } else {
      cout << max(0, i - query(1, 1, n, x, y)) + que(x, y) - que(x + 1, y + 1) << '\n';
    }

  }


}

Compilation message

street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'void update(int, int, int, int, int)':
street_lamps.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'int query(int, int, int, int, int)':
street_lamps.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'void upd(int, int, int)':
street_lamps.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int t = p; t <= vt[i].size(); t += t & -t) {
      |                     ~~^~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int que(int, int)':
street_lamps.cpp:58:10: warning: unused variable 'p' [-Wunused-variable]
   58 |     auto p = lower_bound(vt[i].begin(), vt[i].end(), j) - vt[i].begin() + 1;
      |          ^
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 20844 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 6 ms 18520 KB Output is correct
2 Correct 6 ms 18524 KB Output is correct
3 Correct 5 ms 18524 KB Output is correct
4 Correct 8 ms 18632 KB Output is correct
5 Correct 119 ms 32848 KB Output is correct
6 Correct 263 ms 42080 KB Output is correct
7 Correct 389 ms 50384 KB Output is correct
8 Correct 558 ms 63528 KB Output is correct
9 Correct 98 ms 21712 KB Output is correct
10 Correct 102 ms 23500 KB Output is correct
11 Correct 105 ms 23756 KB Output is correct
12 Correct 548 ms 61104 KB Output is correct
13 Correct 586 ms 62144 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18520 KB Output is correct
2 Incorrect 7 ms 18524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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