Submission #1129473

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1129473	2024-12-25 03:35:25	notkai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3101 ms	246544 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;
#define MAXN 1000000
typedef int i1;
i1 n;
vector<i1> arr(MAXN);
vector<vector<i1>> sortedsegment(4*MAXN,vector<i1>(0));
vector<i1> segment(4*MAXN,0);
void calcsorted(i1 treeindex, i1 onleft=0, i1 onright=n-1){
    for (i1 i = onleft; i <= onright; i++){
        sortedsegment[treeindex].push_back(arr[i]);
    }
    sort(sortedsegment[treeindex].begin(), sortedsegment[treeindex].end());
    if (onleft != onright){
        calcsorted(treeindex*2+1, onleft, (onleft+onright)/2);
        calcsorted(treeindex*2+2, (onleft+onright+2)/2, onright);
    }
}
void calcsegtree(i1 treeindex, i1 onleft = 0, i1 onright = n-1){
    if (onleft == onright){
        segment[treeindex] = 0;
        return;
    }
    calcsegtree(treeindex*2+1, onleft, (onleft+onright)/2);
    calcsegtree(treeindex*2+2, (onleft+onright+2)/2, onright);
    segment[treeindex] = max(segment[treeindex*2+1], segment[treeindex*2+2]);
    i1 maxvalue = sortedsegment[treeindex*2+1][sortedsegment[treeindex*2+1].size()-1];
    auto it = lower_bound(sortedsegment[treeindex*2+2].begin(), sortedsegment[treeindex*2+2].end(), maxvalue);
    if (it != sortedsegment[treeindex*2+2].begin()){
        it--;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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