Submission #1203747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203747		DL_DinhVuMinhHung2k8	Secret (JOI14_secret)	C++20	0 / 100	337 ms	4456 KiB

secret

#ifndef LOCAL
#include "secret.h"
#endif

/** Author: Dinh Vu Minh Hung **/

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif

#define C                make_pair
#define all(a)           (a).begin(), (a).end()
#define ln               '\n'
#define size(a)          ((int)((a).size()))
#define rep(i, n)        for (int i = 0, _n = (n); i < _n; ++i)
#define foru(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b)    for (int i = (a), _b = (b); i >= _b; --i)
#define fi               first
#define se               second
#define eb               emplace_back
#define MASK(i)          (1LL << (i))
#define getbit(x, y)     (((x) >> (y)) & 1LL)
#define turnon(x, y)     ((x) | MASK(y))
#define turnoff(x, y)    ((x) & ~MASK(y))
#define flipbit(x, y)    ((x) ^ MASK(y))
#define bitcnt(x)        __builtin_popcountll(x)
#define TIME             (1.0 * clock() / CLOCKS_PER_SEC)

typedef long double             ld;
typedef long long               ll;
typedef pair<int, int>          ii;
typedef vector<vector<int>>     vii;
typedef vector<vii>             viii;

inline int readInt(){ char c; while (c = getchar(), c != '-' && !isdigit(c)); int n, s = (c == '-');
    n = (s ? getchar() : c) - 48; while (c = getchar(), isdigit(c)) n = (n << 3) + (n << 1) + c - 48; return s ? -n : n; }

inline string readString(){ char c; while (c = getchar(), c == ' ' || c == '\n' || c == '\t');
	string s({c}); while (c = getchar(), c != EOF && c != ' ' && c != '\n' && c != '\t') s += c; return s; }

template <class X, class Y> inline bool maximize(X &a, const Y &b){ return (a < b ? a = b, true : false); }
template <class X, class Y> inline bool minimize(X &a, const Y &b){ return (a > b ? a = b, true : false); }

const int maxn = 1005;

int n, a[maxn], mask[maxn], val[20][maxn];
map<ii, int> mp;

#ifdef LOCAL
void read(){
    cin >> n;
    foru(i, 1, n) cin >> a[i];
}

int Secret(int x, int y){ return min(x + 2 * (y / 2), (int)1e9); }
#endif

void dnc(int l, int r, int lvl = 0){
    if (l == r) return;

    int mid = (l + r) >> 1; mask[mid + 1] ^= MASK(lvl);
    val[lvl][mid] = a[mid], val[lvl][mid + 1] = a[mid + 1];

    ford(i, mid - 1, l) val[lvl][i] = Secret(a[i], val[lvl][i + 1]);
    foru(i, mid + 2, r) val[lvl][i] = Secret(a[i], val[lvl][i - 1]), mask[i] ^= MASK(lvl);

    dnc(l, mid, lvl + 1), dnc(mid + 1, r, lvl + 1);
}

void Init(int N, int A[]){
    n = N;
    rep(i, n) a[i + 1] = A[i];
    dnc(1, n);
}

int Query(int l, int r){
    ++l, ++r;
    if (l == r) return a[l];
    int lvl = __builtin_ctz(mask[l] ^ mask[r]);
    return Secret(val[lvl][l], val[lvl][r]);
}

#ifdef LOCAL
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define name "name"
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    #define NAME "TASK"
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }

    read();
    dnc(1, n);

    cout << Query(0, 3) << ln;
    cout << Query(1, 7) << ln;
    cout << Query(5, 5) << ln;
    cout << Query(2, 4) << ln;

    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}
#endif

• Subtask 1: 0 / 100