oj.uz

Submission #537731

# Submission time Handle Problem Language Result Execution time Memory
537731 2022-03-15T12:43:02 Z cig32 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 964 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
long long bm(long long b, long long p) { 
  if(p==0) return 1;
  long long r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}

int a[MAXN], b[MAXN];
/*
int upper_bound(int l, int r, int v) {
  if(l > r) return -1;
  int ans = -1;
  for(int i=l; i<=r; i++) {
    if(a[i] < v) ans = max(ans, a[i]);
  }
  return ans;
}
 */
struct wavelet_tree {
  int lo, hi;
  wavelet_tree *l, *r;
  int *b, *c, bsz, csz; // c holds the prefix sum of elements

  wavelet_tree() {
    lo = 1;
    hi = 0;
    bsz = 0;
    csz = 0, l = NULL;
    r = NULL;
  }

  void init(int *from, int *to, int x, int y) {
    lo = x, hi = y;
    if(from >= to) return;
    int mid = (lo + hi) >> 1;
    auto f = [mid](int x) {
      return x <= mid;
    };
    b = (int*)malloc((to - from + 2) * sizeof(int));
    bsz = 0;
    b[bsz++] = 0;
    c = (int*)malloc((to - from + 2) * sizeof(int));
    csz = 0;
    c[csz++] = 0;
    for(auto it = from; it != to; it++) {
      b[bsz] = (b[bsz - 1] + f(*it));
      c[csz] = (c[csz - 1] + (*it));
      bsz++;
      csz++;
    }
    if(hi == lo) return;
    auto pivot = stable_partition(from, to, f);
    l = new wavelet_tree();
    l->init(from, pivot, lo, mid);
    r = new wavelet_tree();
    r->init(pivot, to, mid + 1, hi);
  }
  //kth smallest element in [l, r]
  //for array [1,2,1,3,5] 2nd smallest is 1 and 3rd smallest is 2
  int kth(int l, int r, int k) {
    if(l > r) return 0;
    if(lo == hi) return lo;
    int inLeft = b[r] - b[l - 1], lb = b[l - 1], rb = b[r];
    if(k <= inLeft) return this->l->kth(lb + 1, rb, k);
    return this->r->kth(l - lb, r - rb, k - inLeft);
  }
  //count of numbers in [l, r] Less than or equal to k
  int LTE(int l, int r, int k) {
    if(l > r || k < lo) return 0;
    if(hi <= k) return r - l + 1;
    int lb = b[l - 1], rb = b[r];
    return this->l->LTE(lb + 1, rb, k) + this->r->LTE(l - lb, r - rb, k);
  }
  //count of numbers in [l, r] equal to k
  int count(int l, int r, int k) {
    if(l > r || k < lo || k > hi) return 0;
    if(lo == hi) return r - l + 1;
    int lb = b[l - 1], rb = b[r];
    int mid = (lo + hi) >> 1;
    if(k <= mid) return this->l->count(lb + 1, rb, k);
    return this->r->count(l - lb, r - rb, k);
  }
  //sum of numbers in [l ,r] less than or equal to k
  int sum(int l, int r, int k) {
    if(l > r or k < lo) return 0;
    if(hi <= k) return c[r] - c[l - 1];
    int lb = b[l - 1], rb = b[r];
    return this->l->sum(lb + 1, rb, k) + this->r->sum(l - lb, r - rb, k);
  }
  //count max element in [l, r] stricly smaller than k
  int upper_bound(int l, int r, int k) {
    if(l > r) return -1;
    int uwu = LTE(l, r, k - 1);
    if(uwu == 0) return -1;
    return kth(l, r, uwu);
  }
  ~wavelet_tree() {
    delete l;
    delete r;
  }
};

int st[20][MAXN];

int query_max(int l, int r) {
  int k = 32 - __builtin_clz(r-l+1) - 1;
  return max(st[k][l], st[k][r-(1<<k)+1]);
}

int ans[20][MAXN];

void solve(int tc) {
  int n, m;
  cin >> n >> m;
  for(int i=1; i<=n; i++) {
    cin >> a[i];
    st[0][i] = a[i];
  }
  wavelet_tree T;
  T.init(a+1, a+n+1, 0, 1000000000);
  for(int i=1; i<20; i++) {
    for(int j=1; j<=n; j++) {
      if(j+(1<<i)-1 <= n) {
        st[i][j] = max(st[i-1][j], st[i-1][j+(1<<(i-1))]);
      }
    }
  }
  for(int i=1; i<=n; i++) {
    ans[0][i] = -1;
  }
  for(int i=1; i<20; i++) {
    for(int j=1; j<=n; j++) {
      if(j+(1<<i)-1 <= n) {
        ans[i][j] = max(ans[i-1][j], ans[i-1][j+(1<<(i-1))]);
        int q1 = query_max(j, j+(1<<(i-1))-1);
        int q2 = T.upper_bound(j + (1<<(i-1)), j + (1<<i) - 1, q1);
        if(q1 > q2 && q2 != -1) ans[i][j] = max(ans[i][j], q1 + q2);
      }
    }
  }
  while(m--) {
    int l, r, s;
    cin >> l >> r >> s;
    if(l == r) {
      cout << "1\n"; continue;
    }
    int k = 32 - __builtin_clz(r-l+1) - 1;
    int res = max(ans[k][l], ans[k][r-(1<<k)+1]);
    int q1 = query_max(l, l + (1<<k) - 1);
    int q2 = T.upper_bound(l + (1<<k), r, q1);
    if(q1 > q2 && q2 != -1) res = max(res, q1 + q2);
    cout << (res > s ? "0\n" : "1\n");
  }
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 724 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 12 ms 7188 KB Output is correct
12 Correct 40 ms 21596 KB Output is correct
13 Correct 39 ms 21576 KB Output is correct
14 Correct 42 ms 22220 KB Output is correct
15 Correct 46 ms 22220 KB Output is correct
16 Correct 23 ms 5172 KB Output is correct
17 Correct 18 ms 4228 KB Output is correct
18 Correct 22 ms 3924 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 6880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 74864 KB Output is correct
2 Correct 916 ms 76484 KB Output is correct
3 Correct 819 ms 76748 KB Output is correct
4 Correct 843 ms 76632 KB Output is correct
5 Correct 834 ms 76560 KB Output is correct
6 Correct 571 ms 76436 KB Output is correct
7 Correct 588 ms 76552 KB Output is correct
8 Correct 825 ms 76332 KB Output is correct
9 Correct 43 ms 2384 KB Output is correct
10 Correct 842 ms 76372 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 12 ms 7188 KB Output is correct
12 Correct 40 ms 21596 KB Output is correct
13 Correct 39 ms 21576 KB Output is correct
14 Correct 42 ms 22220 KB Output is correct
15 Correct 46 ms 22220 KB Output is correct
16 Correct 23 ms 5172 KB Output is correct
17 Correct 18 ms 4228 KB Output is correct
18 Correct 22 ms 3924 KB Output is correct
19 Runtime error 268 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 12 ms 7188 KB Output is correct
12 Correct 40 ms 21596 KB Output is correct
13 Correct 39 ms 21576 KB Output is correct
14 Correct 42 ms 22220 KB Output is correct
15 Correct 46 ms 22220 KB Output is correct
16 Correct 23 ms 5172 KB Output is correct
17 Correct 18 ms 4228 KB Output is correct
18 Correct 22 ms 3924 KB Output is correct
19 Runtime error 24 ms 6880 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -