oj.uz

Submission #917113

# Submission time Handle Problem Language Result Execution time Memory
917113 2024-01-27T08:42:16 Z duckindog Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 ms 20536 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], cnt[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));
}

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());
  build(1, 1, n);

  for (int i = 1; i <= q; ++i) {
    auto[ty, x, y] = Q[i];
    if (!ty) {
      a[x] = 1 - a[x];
      if (a[x]) {
        update(1, 1, n, i, x);
      } else {

        for (int j = 0; j < querylist.size(); ++j) {
          int l, r; tie(l, r) = querylist[j];
          if (l <= x && x <= r) cnt[j] += max(0, i - query(1, 1, n, l, r));
        }
        update(1, 1, n, 1e8, x);
      }

    } else {
      auto it = lower_bound(querylist.begin(), querylist.end(), make_pair(x, y)) - querylist.begin();
      cout << cnt[it] + max(0, i - query(1, 1, n, x, y)) << '\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 'int32_t main()':
street_lamps.cpp:72:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     auto[ty, x, y] = Q[i];
      |         ^
street_lamps.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int j = 0; j < querylist.size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7628 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 13036 KB Output is correct
2 Correct 123 ms 13256 KB Output is correct
3 Correct 360 ms 13832 KB Output is correct
4 Execution timed out 5043 ms 17084 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7632 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7668 KB Output is correct
5 Correct 100 ms 14164 KB Output is correct
6 Correct 145 ms 15560 KB Output is correct
7 Correct 185 ms 17084 KB Output is correct
8 Correct 244 ms 20536 KB Output is correct
9 Correct 90 ms 13284 KB Output is correct
10 Correct 103 ms 15468 KB Output is correct
11 Correct 100 ms 15292 KB Output is correct
12 Correct 246 ms 18908 KB Output is correct
13 Correct 292 ms 20364 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 8 ms 7516 KB Output is correct
3 Correct 7 ms 7644 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Execution timed out 5084 ms 19000 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7628 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 103 ms 13036 KB Output is correct
9 Correct 123 ms 13256 KB Output is correct
10 Correct 360 ms 13832 KB Output is correct
11 Execution timed out 5043 ms 17084 KB Time limit exceeded
12 Halted 0 ms 0 KB -