oj.uz

Submission #922654

# Submission time Handle Problem Language Result Execution time Memory
922654 2024-02-05T21:52:12 Z myst6 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 1950 ms 108052 KB 
#include <bits/stdc++.h>

using namespace std;

// [3, 5, 1, 8, 4]
// [3, 5, 1, 8, 4]
// each number + the largest one to the left of it, only if it strictly larger
// e.g. 4 + 8 yes
//      8 + 5 no
//      1 + 5 yes
//      5 + 3 yes
// when adding a new entry, update values [i+1, next highest-1]
// but first, undo all changes from indices in the range [i+1, next highest-1]
// [3, 5, 1, 8, 4]
// [0, 0, 0, 0, 8]
// [0, 0, 5, 5, 8]
// [0, 3, 5, 5, 8]
// then do range maximum on that

struct Tree { 
  vector<int> tag, info;
  Tree(int size) { 
    tag.resize(size*4); 
    info.resize(size*4); 
  }
  void pushdown(int x) {
    info[x] += tag[x];
    if (x*2 < tag.size()) tag[x*2] += tag[x];
    if (x*2+1 < tag.size()) tag[x*2+1] += tag[x];
    tag[x] = 0;
  }
  void update(int l, int r, int x, int xl, int xr, int val) {
    if (l > r) return;
    if (l == xl && r == xr) {
      tag[x] = val;
    } else {
      int xm = (xl + xr) / 2;
      update(l, min(r, xm), x*2, xl, xm, val);
      update(max(l, xm+1), r, x*2+1, xm+1, xr, val);
      pushdown(x); pushdown(x*2); pushdown(x*2+1);
      info[x] = max(info[x*2], info[x*2+1]);
    }
  }
  int query(int l, int r, int x, int xl, int xr) {
    if (l > r) return 0;
    pushdown(x);
    if (l == xl && r == xr) {
      return info[x]; 
    } else {
      int xm = (xl + xr) / 2;
      int left = query(l, min(r, xm), x*2, xl, xm);
      int right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
      return max(left, right);
    }
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  vector<int> w(N);
  for (int i=0; i<N; i++) cin >> w[i];
  vector<int> next(N, N);
  stack<int> S;
  for (int i=0; i<N; i++) {
    while (S.size() && w[S.top()] < w[i]) {
      next[S.top()] = i;
      S.pop();
    }
    S.push(i);
  }
  vector<array<int,4>> queries(M);
  for (int i=0; i<M; i++) {
    int l, r, k;
    cin >> l >> r >> k;
    queries[i] = {{l-1, r-1, k, i}};
  }
  sort(queries.rbegin(), queries.rend());
  Tree tree(N);
  vector<int> ans(M);
  int line = N;
  set<int> changes;
  set<int> todo;
  for (int i=0; i<N; i++) todo.insert(i);
  for (int i=0; i<M; i++) {
    int l = queries[i][0], r = queries[i][1];
    int k = queries[i][2], q = queries[i][3];
    while (line > l) {
      line--;
      if (line+1 < next[line]) {
        while (changes.size() && *changes.begin() < next[line]) {
          int idx = *changes.begin();
          tree.update(idx+1, next[idx]-1, 1, 0, N-1, -w[idx]);
          changes.erase(idx);
        }
        while (true) {
          auto it = todo.lower_bound(line+1);
          if (it != todo.end() && *it < next[line]) {
            tree.update(*it, *it, 1, 0, N-1, w[*it]);
            todo.erase(it);
          } else {
            break;
          }
        }
        tree.update(line+1, next[line]-1, 1, 0, N-1, w[line]);
        changes.insert(line);
      }
    }
    // for (int j=0; j<N; j++) cout << tree.query(j, j, 1, 0, N-1) << " "; cout << "\n";
    int cost = tree.query(l, r, 1, 0, N-1);
    if (cost <= k) ans[q] = 1;
  }
  for (int x : ans) cout << x << "\n";
  return 0;
}

Compilation message

sortbooks.cpp: In member function 'void Tree::pushdown(int)':
sortbooks.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if (x*2 < tag.size()) tag[x*2] += tag[x];
      |         ~~~~^~~~~~~~~~~~
sortbooks.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     if (x*2+1 < tag.size()) tag[x*2+1] += tag[x];
      |         ~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1925 ms 107928 KB Output is correct
2 Correct 1950 ms 107928 KB Output is correct
3 Correct 1936 ms 107928 KB Output is correct
4 Correct 1935 ms 108052 KB Output is correct
5 Incorrect 1114 ms 107928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 368 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -