Submission #321745

#	Time	Username	Problem	Language	Result	Execution time	Memory
321745		lohacho	Secret (JOI14_secret)	C++14	100 / 100	519 ms	8428 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)1004;
int val[1004][1004], NN;

void Init(int N, int A[]) {
    NN = N;
    function<void(int, int)> sol = [&](int s, int e){
        if(s == e){
            val[s][e] = A[s];
            return;
        }
        int mid = (s + e) / 2;
        sol(s, mid), sol(mid + 1, e);
        int pos = (s + mid) / 2 + 1;
        for(int i = s; i < mid; ++i){
            while(pos < i){
                pos = (pos + mid) / 2 + 1;
            }
            if(pos > i){
                val[i][mid] = Secret(val[i][pos - 1], val[pos][mid]);
//                cout << i << ' ' << mid << ' ' << val[i][mid] << endl;
            }
        }
        pos = (mid + 1 + e) / 2;
        for(int i = e; i > mid + 1; --i){
            while(pos > i){
                pos = (mid + 1 + pos) / 2;
            }
            if(pos < i){
                val[mid + 1][i] = Secret(val[mid + 1][pos], val[pos + 1][i]);
//                cout << mid + 1 << ' ' << i << ' ' << val[mid + 1][i] << endl;
            }
        }
    };
    sol(0, N - 1);
}

int Query(int L, int R) {
    if(L == R){
        return val[L][R];
    }
    int s = 0, e = NN - 1, mid;
    while(true){
        mid = (s + e) / 2;
        if(L <= mid && R > mid){
            return Secret(val[L][mid], val[mid + 1][R]);
        }
        if(mid < L){
            s = mid + 1;
        }
        else{
            e = mid;
        }
    }
  return 0;
}

• Subtask 1: 100 / 100