제출 #539338

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
539338	2022-03-18 18:05:52	1ne	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	543 ms	262144 KiB

sortbooks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
vector<int64_t>extra;
void combine(vector<int64_t>tree1,vector<int64_t>tree2,int64_t node){
  /*for (auto x:tree1){
    cout<<x<<" ";
  }
  cout<<"     - > ";
  for (auto x:tree2){
    cout<<x<<" ";
  }
  cout<<'\n';
  */
  extra[node] = max(extra[node*2],extra[node*2 + 1]);
  auto right = lower_bound(tree2.begin(),tree2.end(),tree1.back()) - tree2.begin();
  while(right>=0){
    if (tree2[right]>=tree1.back() || right>=(int)tree2.size()){
      --right;
    }
    else break;
  }
  if (right>=0){
    extra[node] = max(extra[node],tree1.back() + tree2[right]);
  }
  // if there is a element in right segment which is less than left maximum
}
void build(vector<vector<int64_t>>&tree,vector<int64_t>&arr,int64_t node,int64_t node_low,int64_t node_high){
    if (node_low==node_high){
        tree[node].push_back(arr[node_low]);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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