제출 #952769

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
952769	2024-03-24 18:51:23	idiotcomputer	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	64 / 100	3058 ms	262148 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 pb push_back
#define pii pair<int,int>
#define f first 
#define s second
const int mxN = 1e6;
int n;
int vals[mxN];
int smax[4*mxN+1];
int ans[4*mxN+1];
vector<int> all[4*mxN+1];
void build(int l = 0, int r = n-1, int idx = 0){
    if (l == r){
        smax[idx] = vals[l];
        ans[idx] = 0;
        all[idx].pb(vals[l]);
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
    smax[idx] = max(smax[2*idx+1],smax[2*idx+2]);
    ans[idx] = max(ans[2*idx+1],ans[2*idx+2]);
    int cidx = lower_bound(all[2*idx+2].begin(),all[2*idx+2].end(),smax[2*idx+1]) - all[2*idx+2].begin();
    if (cidx > 0) ans[idx] = max(ans[idx], smax[2*idx+1] + all[2*idx+2][cidx-1]);
    cidx = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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