oj.uz

답안 #333426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333426 2020-12-05T22:55:59 Z gmyu 비밀 (JOI14_secret) C++14
0 / 100
 505 ms 8940 KB 
/*
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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 135 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 137 ms 4864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 135 ms 4716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 505 ms 8612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 498 ms 8812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 500 ms 8904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 498 ms 8684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 501 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 504 ms 8940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 501 ms 8812 KB Execution killed with signal 11 (could be triggered by violating memory limits)