Submission #1135877

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1135877	2025-01-14 07:33:08	nathan4690	Secret (JOI14_secret)	C++20	100 / 100	345 ms	16296 KiB

secret

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 "secret.h"
int n, a[10005];
int pf[4005][1005], sf[4005][1005];
void build(int idx, int l, int r){
    if(l == r){
        pf[idx][l] = sf[idx][l] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    sf[idx*2][mid] = a[mid];
    for(int i=mid-1;i>=l;i--) sf[idx*2][i] = Secret(a[i], sf[idx*2][i+1]);
    pf[idx*2+1][mid+1] = a[mid+1];
    for(int i=mid+2;i<=r;i++) pf[idx*2+1][i] = Secret(pf[idx*2+1][i-1], a[i]);
    build(idx*2, l, mid);
    build(idx*2+1, mid+1, r);
//    if(l == 0 && r == n-1) return;
//    for(int i=l;i<=mid;i++) pf[idx][i] = pf[idx*2][i];
//    for(int i=mid+1;i<=r;i++) pf[idx][i] = Secret(pf[idx][i-1], a[i]);
//    for(int i=r;i>=mid+1;i--) sf[idx][i] = sf[idx*2+1][i];
//    for(int i=mid;i>=l;i--) sf[idx][i] = Secret(a[i], sf[idx][i+1]);
}
int getRange(int idx, int l, int r, int u, int v){
    int mid = (l + r) / 2;
    if(v <= mid) return getRange(idx*2, l, mid, u, v);
    if(mid < u) return getRange(idx*2+1, mid+1, r, u, v);
    return Secret(sf[idx*2][u], pf[idx*2+1][v]);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 100 / 100