Submission #1256476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256476		kiteyu	Secret (JOI14_secret)	C++17	0 / 100	338 ms	8428 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll Secret(ll x ,ll y){
    return x + y;
}
const int N = 1000;
ll it[4 * N][N + 5];
ll it1[4 * N][N + 5];

ll a[N + 5];
int n;

void build(int id, int l, int r){
    if(l >= r) return;
    int mid = (l + r) >> 1;
    it[id][mid] = a[mid];
    if(mid - 1 >= l){
        it1[id][mid - 1] = a[mid - 1];
        for(int i = mid - 2 ; i >= l ; --i) it1[id][i] = Secret(it1[id][i + 1],a[i]);
    }

    for(int i = mid + 1 ; i <= r ; ++i) it[id][i] = Secret(it[id][i - 1],a[i]);
    build(id << 1,l,mid - 1);
    build(id << 1 | 1,mid + 1,r);
}

ll get(int id, int l, int r, int u, int v){
    int mid = (l + r) >> 1;
    if(u <= mid && mid <= v) {
        if(u == mid) return it[id][v];
        return Secret(it1[id][u],it[id][v]);
    }
    if(mid < u) return get(id << 1 | 1,mid + 1,r,u,v);
    else return get(id << 1,l,mid - 1,u,v);
}


void Init(int nn, int A[]){
    n = nn;
    for(int i = 1 ; i <= n ; ++i) a[i] = A[i - 1];
    build(1,1,n);
}

int Query(int l, int r){
    l++;r++;
    if(l > r) swap(l,r);
    if(l == r) return a[l];
    return get(1,1,n,l,r);
}

• Subtask 1: 0 / 100