oj.uz

Submission #537715

# Submission time Handle Problem Language Result Execution time Memory
537715 2022-03-15T12:02:45 Z cig32 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 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];
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;
}

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];
  for(int x: s) {
    is[x] = ++bruh;
  }
  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 = 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 = 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);
}

/*
7 1
4 9 1 0 4 0 8 
4 7 4
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 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 1 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 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 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 4 ms 1036 KB Output is correct
12 Correct 16 ms 2352 KB Output is correct
13 Correct 17 ms 2436 KB Output is correct
14 Correct 19 ms 2496 KB Output is correct
15 Correct 18 ms 2480 KB Output is correct
16 Correct 17 ms 2516 KB Output is correct
17 Correct 10 ms 2132 KB Output is correct
18 Runtime error 18 ms 2508 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 1756 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 Execution timed out 3072 ms 21640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 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 4 ms 1036 KB Output is correct
12 Correct 16 ms 2352 KB Output is correct
13 Correct 17 ms 2436 KB Output is correct
14 Correct 19 ms 2496 KB Output is correct
15 Correct 18 ms 2480 KB Output is correct
16 Correct 17 ms 2516 KB Output is correct
17 Correct 10 ms 2132 KB Output is correct
18 Runtime error 18 ms 2508 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 1 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 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 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 4 ms 1036 KB Output is correct
12 Correct 16 ms 2352 KB Output is correct
13 Correct 17 ms 2436 KB Output is correct
14 Correct 19 ms 2496 KB Output is correct
15 Correct 18 ms 2480 KB Output is correct
16 Correct 17 ms 2516 KB Output is correct
17 Correct 10 ms 2132 KB Output is correct
18 Runtime error 18 ms 2508 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -