Submission #1174992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174992		julia_08	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1090 ms	115160 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

struct event{
  int x, t, i;

  bool operator < (event other){
    if(x != other.x) return x > other.x;
    if(t != other.t) return t < other.t;
    return i < other.i;
  }

};

int w[MAXN], l[MAXN], r[MAXN], k[MAXN];

int ans[MAXN];

int seg[4 * MAXN];

vector<event> all_events;
vector<vector<event>> sorted_events;

void update(int x, int lx, int rx, int i, int val){

  if(rx < i || lx > i) return;

  if(lx == rx){
    seg[x] = val;
    return;
  }

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  update(lc, lx, m, i, val);
  update(rc, m + 1, rx, i, val);

  seg[x] = max(seg[lc], seg[rc]);
}

int query(int x, int lx, int rx, int l, int r){

  if(rx < l || lx > r) return 0;

  if(l <= lx && rx <= r) return seg[x];

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  return max(query(lc, lx, m, l, r), query(rc, m + 1, rx, l, r));
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, m; cin >> n >> m;

  for(int i=1; i<=n; i++){
    cin >> w[i];
  }

  stack<int> q;

  for(int i=1; i<=n; i++){

    while(!q.empty() && w[q.top()] <= w[i]) q.pop();

    if(!q.empty()) all_events.push_back({q.top(), 0, i});

    q.push(i);

  }

  for(int i=1; i<=m; i++){
    cin >> l[i] >> r[i] >> k[i];
    all_events.push_back({l[i], 1, i});
  }

  sort(all_events.begin(), all_events.end());

  int last_x = -1e9;

  for(auto &ev : all_events){

    if(ev.x != last_x){
      last_x = ev.x;
      sorted_events.push_back({});
    }

    sorted_events.back().push_back(ev);
    
  }

  for(auto &evs : sorted_events){
    for(auto &ev : evs){

      if(ev.t == 0){
        update(1, 1, n, ev.i, w[ev.x] + w[ev.i]);

      } else{
        ans[ev.i] = query(1, 1, n, l[ev.i], r[ev.i]);
      }

    }
  }

  for(int i=1; i<=m; i++) cout << (ans[i] <= k[i]) << "\n";

  return 0;
}

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