oj.uz

Submission #537682

# Submission time Handle Problem Language Result Execution time Memory
537682 2022-03-15T11:22:16 Z cig32 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 914 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + 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;
}

struct wavelet_tree{
	#define vi vector<int>
	#define pb push_back
	int lo, hi;
	wavelet_tree *l, *r;
	vi b;
 
	//nos are in range [x,y]
	//array indices are [from, to)
	wavelet_tree(int *from, int *to, int x, int y){
		lo = x, hi = y;
		if(lo == hi or from >= to) return;
		int mid = (lo+hi)/2;
		auto f = [mid](int x){
			return x <= mid;
		};
		b.reserve(to-from+1);
		b.pb(0);
		for(auto it = from; it != to; it++)
			b.pb(b.back() + f(*it));
		//see how lambda function is used here	
		auto pivot = stable_partition(from, to, f);
		l = new wavelet_tree(from, pivot, lo, mid);
		r = new wavelet_tree(pivot, to, mid+1, hi);
	}
 
	//kth smallest element in [l, r]
	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];
		int lb = b[l-1]; //amt of nos in first (l-1) nos that go in left 
		int rb = b[r]; //amt of nos in first (r) nos that go in left
		if(k <= inLeft) return this->l->kth(lb+1, rb , k);
		return this->r->kth(l-lb, r-rb, k-inLeft);
	}
 
	//count of nos in [l, r] Less than or equal to k
	int LTE(int l, int r, int k) {
		if(l > r or 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 nos in [l, r] equal to k
	int count(int l, int r, int k) {
		if(l > r or k < lo or k > hi) return 0;
		if(lo == hi) return r - l + 1;
		int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
		if(k <= mid) return this->l->count(lb+1, rb, k);
		return this->r->count(l-lb, r-rb, k);
	}

  //count max element in [l, r] stricly smaller than k
  int upper_bound(int l, int r, int k) {
    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 min(st[k][l], st[k][r-(1<<k)+1]);
}

int ans[20][MAXN];

void solve(int tc) {
  int n, m;
  cin >> n >> m;
  int a[n+1];
  for(int i=1; i<=n; i++) {
    cin >> a[i];
    st[0][i] = a[i];
  }
  wavelet_tree T(a+1, a+n+1, 1, 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;
    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);
}

/*
5 2
3 5 1 8 2
1 3 6
2 5 3
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 3 ms 2132 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 3 ms 2132 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 11 ms 5076 KB Output is correct
12 Correct 34 ms 14716 KB Output is correct
13 Correct 35 ms 14760 KB Output is correct
14 Correct 37 ms 15212 KB Output is correct
15 Correct 37 ms 15304 KB Output is correct
16 Correct 19 ms 2388 KB Output is correct
17 Correct 14 ms 2048 KB Output is correct
18 Runtime error 13 ms 3052 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 357 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 3 ms 2132 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 11 ms 5076 KB Output is correct
12 Correct 34 ms 14716 KB Output is correct
13 Correct 35 ms 14760 KB Output is correct
14 Correct 37 ms 15212 KB Output is correct
15 Correct 37 ms 15304 KB Output is correct
16 Correct 19 ms 2388 KB Output is correct
17 Correct 14 ms 2048 KB Output is correct
18 Runtime error 13 ms 3052 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 3 ms 2132 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 11 ms 5076 KB Output is correct
12 Correct 34 ms 14716 KB Output is correct
13 Correct 35 ms 14760 KB Output is correct
14 Correct 37 ms 15212 KB Output is correct
15 Correct 37 ms 15304 KB Output is correct
16 Correct 19 ms 2388 KB Output is correct
17 Correct 14 ms 2048 KB Output is correct
18 Runtime error 13 ms 3052 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -