제출 #1032787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032787		pera	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2130 ms	75752 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int n , m;
vector<int> w(N) , ans(N) , r(N) , t(4 * N);
vector<tuple<int , int , int>> query[N];
void upd(int u , int l , int r , int pos , int x){
   if(l == r){
      t[u] = x;
      return;
   }
   int m = (l + r) / 2;
   if(pos <= m){
      upd(u * 2 , l , m , pos , x);
   }else{
      upd(u * 2 + 1 , m + 1 , r , pos , x);
   }
   t[u] = max(t[u * 2] , t[u * 2 + 1]);
}
int GET(int u , int l , int r , int L , int R){
   if(l > r || r < L || l > R){
      return 0;
   }
   if(L <= l && r <= R){
      return t[u];
   }
   int m = (l + r) / 2;
   return max(GET(u * 2 , l , m , L , R) , GET(u * 2 + 1 , m + 1 , r , L , R));
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin >> n >> m;
   for(int i = 1;i <= n;i ++){
      cin >> w[i];
   }
   for(int i = 1;i <= m;i ++){
      int l , r , k;
      cin >> l >> r >> k;
      query[l].push_back({r , k , i});
   }
   for(int i = n;i >= 1;i --){
      r[i] = i + 1;
      while(r[i] <= n && w[i] > w[r[i]]){
         upd(1 , 1 , n , r[i] , w[r[i]] + w[i]);
         r[i] = r[r[i]];
      }
      for(auto [r , k , id] : query[i]){
         ans[id] = GET(1 , 1 , n , i , r) <= k;
      }
   }
   for(int i = 1;i <= m;i ++){
      cout << ans[i] << endl;
   }
}

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