oj.uz

Submission #333423

# Submission time Handle Problem Language Result Execution time Memory
333423 2020-12-05T22:29:05 Z gmyu Secret (JOI14_secret) C++14
0 / 100
 508 ms 8812 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
*/
int rqN;
vi x;
map<pair<int, int>, int> ans;

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



int getAns(int v1, int v2) {
    if(v1>v2) swap(v1, v2);
    pii vp = mp(v1, v2);
    if(ans.find(vp) == ans.end()) ans[vp] = Secret(v1, v2);
    return ans[vp];
}

void divi(int l, int r, int lev = 0) { // generate dat and mask
    if (l == r) 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]);
    for(int i = m+1; i <= r; i++) rqmask[i] ^= 1<<lev;
    divi(l,m,lev+1); divi(m+1,r,lev+1);
}
int que(int l, int r) {         /// [ , ]
    if(l == r) return x[l];
    int bits = __builtin_ctz(rqmask[l]^rqmask[r]);
    return Secret(rq[bits][l], rq[bits][r]);
}

void Init(int N, int A[]) {
    rqN = N;
    for(int i = 0; i < N; i++) x.pb(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:100:1: warning: no return statement in function returning non-void [-Wreturn-type]
  100 | }
      | ^
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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 4716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 138 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 136 ms 4716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 499 ms 8684 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 498 ms 8704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 501 ms 8676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 508 ms 8812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 504 ms 8684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 504 ms 8684 KB Execution killed with signal 11 (could be triggered by violating memory limits)