제출 #631582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631582		bachhoangxuan	비밀 (JOI14_secret)	C++17	100 / 100	472 ms	8304 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
#define MAX_VALUE 1000000000
#define maxn 1005
int dist[maxn][maxn],a[maxn],n;
/*
int Secret(int X,int Y){
    return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
}
*/
void update(int l,int r){
    if(l>r) return;
    if(l==r){
        dist[l][r]=a[r];
        return;
    }
    int mid=(l+r)>>1;
    dist[mid][mid]=a[mid];
    if(l<mid) dist[mid][mid-1]=a[mid-1];
    for(int i=mid+1;i<=r;i++) dist[mid][i]=Secret(dist[mid][i-1],a[i]);
    for(int i=mid-2;i>=l;i--) dist[mid][i]=Secret(a[i],dist[mid][i+1]);
    update(l,mid-1);update(mid+1,r);
}
int get(int l,int r,int tl,int tr){
    int mid=(l+r)>>1;
    if(mid>=tl && mid<=tr){
        if(mid==tl) return dist[mid][tr];
        else return Secret(dist[mid][tl],dist[mid][tr]);
    }
    if(mid<tl) return get(mid+1,r,tl,tr);
    else return get(l,mid-1,tl,tr);
}
void Init(int N, int A[]){
    n=N;
    for(int i=0;i<N;i++) a[i+1]=A[i];
    update(1,n);
}
int Query(int L, int R) {
    L++;R++;
    return get(1,n,L,R);
}
/*
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    Init(n,a);
    int q;cin >> q;
    while(q--){
        int l,r;cin >> l >> r;
        cout << Query(l,r) << '\n';
    }
}
*/

• Subtask 1: 100 / 100