Submission #1156317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156317		KaleemRazaSyed	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1911 ms	205608 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;

const int M = 2 << 20, N = (1 << 20), inf = 1e9;
struct node {
  vector<int> vec;
  int mi; 
} seg[M];
int n, m, a[N];

void build(int s = 0, int e = n, int v = 1)
{
  if(e - s == 1)
    {
      seg[v].mi = 0;
      seg[v].vec = {a[s]};
      return;
    }

  int mid = (s + e) / 2, lc = 2 * v ,rc = lc + 1;
  build(s, mid, lc);
  build(mid, e, rc);

  seg[v].mi = max(seg[lc].mi, seg[rc].mi);

  vector<int> &l = seg[lc].vec;
  vector<int> &r = seg[rc].vec;
  
  
  int i = 0, j = 0;
  while(i < l.size() || j < r.size())
    {
      if(i == l.size() || (j < r.size() && l[i] >= r[j]))
	{
	  seg[v].vec.push_back(r[j]), j++;
	  if(i < l.size()) seg[v].mi = max(seg[v].mi, r[j] + l[i]);
	}
      else
	seg[v].vec.push_back(l[i]), i++;
    }
}

int x;
int get(int l, int r, int s = 0, int e = n, int v = 1)
{
  if(r <= s || e <= l) return 0;
  if(l <= s && e <= r)
    {
      int ans = seg[v].mi;
      auto it = lower_bound(seg[v].vec.begin(), seg[v].vec.end(), x);
      
      if(it != seg[v].vec.begin())
	{
	  it--;
	  ans = max(ans, x + *it);
	}
      x = max(x, seg[v].vec.back());
      return ans;
    }

  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  int ans = get(l, r, s, mid, lc);
  ans = max(ans, get(l, r, mid, e, rc));
  return ans;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  cin >> n >> m;
  for(int i = 0; i < n; i ++)
    cin >> a[i];
  
  build();

  while(m--)
    {
      int l, r, k;
      cin >> l >> r >> k;
      l--;
      x = -inf;
      int res = get(l, r);
      cout << (res <= k) << '\n';
    }
  return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23