Submission #333426

#	Time	Username	Problem	Language	Result	Execution time	Memory
333426		gmyu	Secret (JOI14_secret)	C++14	0 / 100	505 ms	8940 KiB

secret

/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

#include "secret.h"

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 1007
#define MAXE 100007


bool debug = false, submit = true;

/**
* RMQ use sparse table, O(N log N) memory and setip, O(1) query
* https://usaco.guide/plat/DC-SRQ
*/
int rqN;
int x[MAXV];

int rq[MAXV][MAXV];      /// 18 = ceil(log2(n))


void divi(int l, int r, int lev = 0) { // generate dat and mask
    if (l == r) { rq[lev][l] = x[l]; return; }
    int m = (l+r)/2;
    rq[lev][m] = x[m]; for(int i = m-1; i >= l; i--) rq[lev][i] = Secret(x[i], rq[lev][i+1]);
    rq[lev][m+1] = x[m+1]; for(int i = m+2; i <= r; i++) rq[lev][i] = Secret(rq[lev][i-1], x[i]);
    divi(l,m,lev+1); divi(m+1,r,lev+1);
}
int que(int ql, int qr, int lev = 0, int l = 0, int r = rqN -1) {         /// [ , ]
    if(l == r) return x[l];
    int m = (l+r)/2;
    if(ql <= m && m <= qr) return Secret(rq[lev][ql], rq[lev][qr]);
    if(qr <= m) return que(ql, qr, lev+1, l, m);
    else return que(ql, qr, lev+1, m+1, r);
}

void Init(int N, int A[]) {
    rqN = N;
    for(int i = 0; i < N; i++) x[i]= A[i];
    divi(0, N-1);
}
int Query(int L, int R) {
    que(L, R);
}

Compilation message (stderr)

secret.cpp: In function 'int Query(int, int)':
secret.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
   74 | }
      | ^

• Subtask 1: 0 / 100