oj.uz

답안 #537687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537687 2022-03-15T11:27:08 Z cig32 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 845 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;
}

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 max(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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 4 ms 2004 KB Output is correct
7 Correct 3 ms 2004 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 4 ms 2004 KB Output is correct
7 Correct 3 ms 2004 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 10 ms 4948 KB Output is correct
12 Correct 36 ms 14548 KB Output is correct
13 Correct 37 ms 14496 KB Output is correct
14 Correct 38 ms 15024 KB Output is correct
15 Correct 35 ms 14936 KB Output is correct
16 Correct 20 ms 2196 KB Output is correct
17 Correct 15 ms 1876 KB Output is correct
18 Runtime error 10 ms 2772 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 376 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 845 ms 50736 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 4 ms 2004 KB Output is correct
7 Correct 3 ms 2004 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 10 ms 4948 KB Output is correct
12 Correct 36 ms 14548 KB Output is correct
13 Correct 37 ms 14496 KB Output is correct
14 Correct 38 ms 15024 KB Output is correct
15 Correct 35 ms 14936 KB Output is correct
16 Correct 20 ms 2196 KB Output is correct
17 Correct 15 ms 1876 KB Output is correct
18 Runtime error 10 ms 2772 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 4 ms 2004 KB Output is correct
7 Correct 3 ms 2004 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 10 ms 4948 KB Output is correct
12 Correct 36 ms 14548 KB Output is correct
13 Correct 37 ms 14496 KB Output is correct
14 Correct 38 ms 15024 KB Output is correct
15 Correct 35 ms 14936 KB Output is correct
16 Correct 20 ms 2196 KB Output is correct
17 Correct 15 ms 1876 KB Output is correct
18 Runtime error 10 ms 2772 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -