oj.uz

Submission #333426

# Submission time Handle Problem Language Result Execution time Memory
333426 2020-12-05T22:55:59 Z gmyu Secret (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

# Verdict Execution time Memory 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)