oj.uz

답안 #537718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537718 2022-03-15T12:13:35 Z cig32 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 1812 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) {
    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];
int a[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];
  }
  set<int> s;
  for(int i=1; i<=n; i++) s.insert(a[i]);
  unordered_map<int, int> is;
  int bruh= 0;
  int b[n+1];
  int wtf[n+1];
  for(int x: s) {
    is[x] = ++bruh;
    wtf[bruh] = x;
  }
  for(int i=1; i<=n; i++) {
    b[i] = is[a[i]];
  }
  wavelet_tree T(b+1, b+n+1, 1, 1000000);
  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, is[q1]);
        if(q2 != -1) q2 = wtf[q2];
        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, is[q1]);
    if(q2 != -1) q2 = wtf[q2];
    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 1
0 0 8 6 8 
4 5 7
*/

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 592 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 592 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 6 ms 980 KB Output is correct
12 Correct 23 ms 2412 KB Output is correct
13 Correct 17 ms 2452 KB Output is correct
14 Correct 19 ms 2516 KB Output is correct
15 Correct 26 ms 2436 KB Output is correct
16 Correct 16 ms 2528 KB Output is correct
17 Correct 12 ms 2132 KB Output is correct
18 Runtime error 9 ms 2504 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 592 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 6 ms 980 KB Output is correct
12 Correct 23 ms 2412 KB Output is correct
13 Correct 17 ms 2452 KB Output is correct
14 Correct 19 ms 2516 KB Output is correct
15 Correct 26 ms 2436 KB Output is correct
16 Correct 16 ms 2528 KB Output is correct
17 Correct 12 ms 2132 KB Output is correct
18 Runtime error 9 ms 2504 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 592 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 6 ms 980 KB Output is correct
12 Correct 23 ms 2412 KB Output is correct
13 Correct 17 ms 2452 KB Output is correct
14 Correct 19 ms 2516 KB Output is correct
15 Correct 26 ms 2436 KB Output is correct
16 Correct 16 ms 2528 KB Output is correct
17 Correct 12 ms 2132 KB Output is correct
18 Runtime error 9 ms 2504 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -