oj.uz

Submission #333431

# Submission time Handle Problem Language Result Execution time Memory
333431 2020-12-05T23:14:32 Z gmyu Secret (JOI14_secret) C++14
100 / 100
 515 ms 4476 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

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
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
* example problem: https://oj.uz/problem/view/JOI14_secret
*/
int rmqN, rmqRange[2];
int rmqX[MAXV];
int rmq[12][MAXV];      /// 18 = ceil(log2(n))

void divi(int l = rmqRange[0], int r = rmqRange[1], int lev = 0) { // generate dat and mask
    if (l == r) { return; }
    int m = (l+r)/2;
    rmq[lev][m] = rmqX[m];     for(int i = m-1; i >= l; i--) rmq[lev][i] = Secret(rmqX[i], rmq[lev][i+1]);
    rmq[lev][m+1] = rmqX[m+1]; for(int i = m+2; i <= r; i++) rmq[lev][i] = Secret(rmq[lev][i-1], rmqX[i]);
    divi(l,m,lev+1); divi(m+1,r,lev+1);
}
int que(int ql, int qr, int lev = 0, int l = rmqRange[0], int r = rmqRange[1]) {         /// [ , ]
    if(l == r) return rmqX[l];
    int m = (l+r)/2;
    if(ql <= m && m+1 <= qr) return Secret(rmq[lev][ql], rmq[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[]) {
    for(int i = 0; i < N; i++) rmqX[i]= A[i];
    rmqN = N; rmqRange[0] = 0; rmqRange[1] = N-1;
    divi();
}
int Query(int L, int R) {
    return que(L, R);
}

Compilation message

secret.cpp: In function 'void setIO(std::string)':
secret.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
secret.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2412 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 146 ms 2392 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 2412 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 514 ms 4400 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 507 ms 4476 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 511 ms 4344 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 513 ms 4412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 515 ms 4364 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 515 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 510 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1